Supervised Distributed Computing: Efficiency and Robustness under a Majority of Adversarial Workers
For distributed computing with untrusted workers, this work provides a practical solution that maintains efficiency and robustness under a majority of adversarial workers, addressing a key bottleneck in the master-worker model.
This paper extends the supervised distributed computing paradigm to handle any constant fraction β<1 of adversarial workers, achieving robust and efficient computation where honest workers perform close to a single execution per task, significantly outperforming existing robust master-worker and peer-to-peer approaches.
We consider a recently proposed \emph{supervised distributed computing} paradigm \cite{augustine2025supervised} that extends and refines the standard master-worker paradigm for parallel computations. In this paradigm, there is a supervisor, a source, a target, and a collection of workers. The distributed computation is given as an acyclic task graph that is known to the supervisor. The source initially stores the input and the target is supposed to store the output of the computation. The individual tasks of the computation are supposed to be executed by the workers under the guidance of the supervisor. The source, target and supervisor are assumed to be reliable, while a $β$-fraction of the workers might be adversarial, for some $β\in [0,1)$. This covers, for example, the case where a supervisor has to work with untrusted volunteers. In the standard master-worker approach, the master checks whether the workers correctly execute the assigned tasks, creating a severe bottleneck, whereas in the supervised approach, the supervisor outsources this checking to the workers. Prior to this work, only supervised solutions were known for the case that $β$ is a sufficiently small constant. We show that robust and efficient supervised solutions are possible for \emph{any} constant $β<1$ while the expected work for the honest workers is close to a \emph{single} execution per task, given that there is a lightweight verification mechanism that allows honest workers to check the correctness of task outputs, which is significantly better than all robust master-worker as well as peer-to-peer approaches known so far.