Supervised Distributed Computing

Abstract

I will introduce a new framework for distributed computing called supervised distributed computing that extends and refines the standard master-worker approach of scheduling multi-threaded computations. In this framework, there are different roles: a supervisor, a source, a target, and a collection of workers. Initially, the source stores some instance $I$ of a computational problem, and at the end, the target is supposed to store a correct solution $S(I)$ for that instance. We assume that the computation required for $S(I)$ can be modeled as a directed acyclic graph $G=(V,E)$, where $V$ is a set of tasks and $(v,w)\in E$ if and only if task $w$ needs information from task $v$ in order to be executed. Given $G$, the role of the supervisor is to schedule the execution of the tasks in $G$ by assigning them to the workers. If all workers are honest, the workers have access to the source and target, and information can be exchanged directly between the workers, the supervisor only needs to know $G$ to successfully schedule the computations. I.e., the supervisor does not have to handle any data itself like in standard master-worker approaches, which has the tremendous benefit that tasks can be run massively in parallel in large distributed environments without the supervisor becoming a bottleneck. But what if some of the workers are adversarial? Interestingly, I will show that under certain assumptions a data-agnostic scheduling approach would even work in an adversarial setting where the majority of workers is adversarial while keeping the work overhead for the honest workers close to the case that all workers are honest. The details of our results can be found in [1, 2]