| Paper ID | D3-S4-T1.2 |
| Paper Title |
List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier |
| Authors |
Mahdi Soleymani, University of Michigan, United States; Ramy E. Ali, University of Southern California, United States; Hessam Mahdavifar, University of Michigan, United States; A. Salman Avestimehr, University of Southern California, United States |
| Session |
D3-S4-T1: Distributed Computation II |
| Chaired Session: |
Wednesday, 14 July, 23:00 - 23:20 |
| Engagement Session: |
Wednesday, 14 July, 23:20 - 23:40 |
| Abstract |
We consider the problem of coded computing where a computational task is performed in a distributed fashion in the presence of adversarial workers. We propose techniques to break the adversarial toleration threshold barrier previously known in coded computing. More specifically, we leverage list-decoding techniques for folded Reed-Solomon codes and propose novel algorithms to recover the correct codeword using side information. In the coded computing setting, we show how the master node can perform certain carefully designed extra computations to obtain the side information. This side information is then utilized to prune the output of list decoder and uniquely recover the true outcome. We further propose folded Lagrange coded computing (FLCC) to incorporate the developed techniques into a specific coded computing setting. Our results show that FLCC outperforms LCC by breaking the barrier on the number of adversaries that can be tolerated. In particular, the corresponding threshold in FLCC is improved by a factor of two compared to that of LCC.
|
