Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing
Tayyebeh Jahani-Nezhad, Mohammad Ali Maddah-Ali
Abstract
One of the major challenges in using distributed learning to train complicated models with large data sets is to deal with stragglers effect. As a solution, coded computation has been recently proposed to efficiently add redundancy to the computation tasks. In this technique, coding is used across data sets, and computation is done over coded data, such that the results of an arbitrary subset of worker nodes with a certain size are enough to recover the final results. The major drawbacks with those approaches are (1) they are limited to polynomial functions, (2) the number of servers that we need to wait for grows with the degree of the model, (3) they are not numerically stable for computation over real numbers. In this paper, we propose Berrut Approximated Coded Computing (BACC), as an alternative approach, as a numerically stable solution, which works beyond polynomial functions computation and with any number of servers. The accuracy of the approximation is established theoretically and verified by simulation. In particular, BACC is used to train a deep neural network on a cluster of servers, which outperforms alternative uncoded solutions in terms of the rate of convergence.