Berrut Approximated Coded Computing for Straggler-Resilient Non-Polynomial Distributed Computation

A numerically stable straggler-resilient coded computing scheme over the real numbers R for approximately evaluating arbitrary (possibly non-polynomial) functions f: V -> U across K input data blocks X = (X_0, ..., X_{K-1}) using N + 1 worker nodes, in which the master encodes the dataset via Berrut's pole-free barycentric rational interpolant u(z) = sum_{i=0}^{K-1} (((-1)^i / (z - alpha_i)) / sum_{j=0}^{K-1} ((-1)^j / (z - alpha_j))) X_i at first-kind Chebyshev nodes alpha_j = cos((2j + 1) pi / (2K)), assigns coded shares X_hat_r = u(z_r) at second-kind Chebyshev nodes z_r = cos(r pi / N) to workers r in {0, ..., N}, and decodes f(X_j) approx r_{Berrut, F}(alpha_j) in O(|F|) time from any subset F of n + 1 = N + 1 - s non-straggling worker evaluations f(u(z_tilde_i)) using Berrut's rational interpolant r_{Berrut, F}(z) = sum_{i=0}^n (((-1)^i / (z - z_tilde_i)) / sum_{j=0}^n ((-1)^j / (z - z_tilde_j))) f(u(z_tilde_i)).