Analog Lagrange Coded Computing: On the Curious Case of Adversarial Workers

Coded Computing is a modern paradigm of distributed computing wherein certain computations over a dataset can be efficiently performed using distributed worker nodes while addressing various challenges such as privacy of data and resiliency from stragglers. Within this class, Analog Lagrange Coded Computing (ALCC) is one such scheme that performs computations over a dataset of infinite fields through floating point implementation. As a result, ALCC is known to outperform its digital counterpart, which inherently suffers from computation overflows due to finite field operations. Despite these benefits, it is known that ALCC cannot be implemented with worker nodes that return erroneous computation results. Pointing at this limitation, in this work, we propose an enhanced version of ALCC to work in the presence of a certain number of adversarial worker nodes. At the heart of the contribution lies the use of error-correction algorithms for Discrete Fourier Transform (DFT) codes along with ALCC. First, we analyze the effect of precision errors on the DFT decoder in ALCC and then propose some novel encoding and decoding algorithms to improve the accuracy of ALCC despite the presence of adversarial workers.