Supervised Distributed Computing

John Augustine, Christian Scheideler, Julian Werthmann · 2025

Read Supervised Distributed Computing by John Augustine, Christian Scheideler, Julian Werthmann (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-11600.txt.

Introduction

John Augustine, Christian Scheideler, and Julian Werthmann introduced a framework in twenty twenty-five for splitting computing work across many machines. In the classic setup, a boss machine hands out tasks and moves all the data itself, which can slow large jobs. Their setup adds clear roles: a source holds the problem, a target receives the answer, workers do the tasks, and a supervisor schedules them.

The supervisor needs to know only the task graph, the map of which task feeds which. It touches no data, so work can run hugely in parallel without a bottleneck. The authors show the scheme still works when a fixed share of workers cheats, at no large extra cost. They prove this with worked designs for matrix multiplication and sorting.

Catalog record

CREATORJohn Augustine, Christian Scheideler, Julian Werthmann
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE110 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-11600

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Supervised Distributed Computing Thanks: John Augustine is supported by the Centre for Cybersecurity, Trust and Reliability (CyStar), IIT Madras. Christian Scheideler and Julian Werthmann are funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 549499840. John Augustine, Christian Scheideler, Julian Werthmann Abstract We introduce a new framework for 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 I of a computational problem, and at the end, the target is supposed to store a correct solution S ⁡ ( I ) S(I) for that instance. We assume that the computation required for S ⁡ ( I ) S(I) can be modeled as a directed acyclic graph G = ( V , E ) G=(V,E) , where V V is a set of tasks and ( v , w ) ∈ E (v,w)\in E if and only if task w w needs information from task v v in order to be executed. Given G G , the role of the supervisor is to schedule the execution of the tasks in G G by assigning them to the workers. If all workers are honest, information can be exchanged between the workers, and the workers have access to the source and target, the supervisor only needs to know G 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 a constant fraction of the workers is adversarial? Interestingly, we show that under certain assumptions a data-agnostic scheduling approach would even work in an adversarial setting without (asymptotically) increasing the work required for communication and computations. We demonstrate the validity of these assumptions by presenting concrete solutions for supervised matrix multiplication and sorting. 1 Introduction There is a long line of work in the literature on scheduling multithreaded computations (see, e.g., [ 22 ] for a survey). Many approaches follow the master-worker paradigm, where a master delivers tasks among workers and collects their outcomes. In the most simple setting, there is a single master that delivers all work, but this limits scalability. However, with approaches such as MapReduce, where every worker can become a master as well so that work can be delivered recursively, the scalability can be significantly increased. In massive computations using a large number of workers, it cannot be assumed that all workers work reliably all the time. Therefore, suitable mechanisms are needed to obtain a desired degree of reliability. In the Hadoop MapReduce framework, for example, a worker is expected to report back periodically to its master with completed work and status updates. If a worker falls silent for longer than a given interval, the master records the worker as dead and sends the work assigned to that worker to another worker [ 32 ] . While in a closed or trusted environment, it is reasonable to assume that the worst case that can happen to workers are crash failures, in situations where work leaves a trusted environment, one also has to worry about adversarial behavior. A popular approach where such behavior has to be taken into account is volunteer-based computing. An early example of this computing approach is SETI@home (1998-2020), where tasks were given to volunteers to analyze astronomical data for extraterrestrial life. To prevent cheating, SETI@home gave each task to two volunteers. If their results disagree, additional volunteers would be contacted for that task until enough results agree. Its follow-up service, BOINC, is nowadays used for a wide range of scientific computations. SETI@home and BOINC [ 4 ] both follow the approach that all tasks are delivered by a trusted server since it appears to be challenging to apply the MapReduce paradigm in a setting with untrusted volunteers. This server has to receive all input data from some source, which can be problematic for applications with massive amounts of data, like in data science and natural sciences, since that creates a bottleneck. If, instead, the server could just focus on scheduling computations without handling input and output data, it would be easy for a single server to schedule even millions of tasks. In fact, a recent study has shown that such an approach would indeed be beneficial [ 26 ] . Thus, we will address the following central question: Can the handling of data be decoupled from the problem of scheduling the execution of tasks, even under adversarial behavior of some of the workers? At first glance, that looks like a bad idea because how can a server know that tasks were executed correctly if it does not see the input or output. Alternatively, the source could do the checking, but the source might not have or be willing to provide the resources for output verifications. Thus, we are left with the workers. If there is an output verification mechanism for the tasks whose runtime is much lower than executing a task, an obvious strategy for the server would be the following: Ask a single worker to execute a task (based on input provided by the source) and send its output to a quorum of workers for verification. Suppose that the fraction of adversarial workers is sufficiently small and the quorum consists of a logarithmic number of randomly chosen workers. Then one can easily prove that if a majority of workers in that quorum tells the server that the output is correct, at least one honest worker in that quorum received the correct output, with high probability, irrespective of whether the executing worker is adversarial or not. However, for any constant fraction \beta of adversarial workers with \beta>0 , this approach has an inherent communication overhead of a logarithmic factor (given that the verification mechanism cannot easily be turned into a robust distributed version) because a logarithmic number of quorum members is necessary to be able to trust the quorum vote with high probability, and, in general, the quorum members need to know the entire input to be able to check whether the output is correct. Thus, the following question arises: Is there a data-agnostic scheduling approach with a constant factor overhead for the computation and the communication? Interestingly, for the case that computations are given as task graphs, we present a general framework that can achieve a constant factor overhead given that a lightweight verification mechanism is available for the tasks. Moreover, we demonstrate the validity of that assumption by presenting solutions for two standard problems: sorting and matrix multiplication. Our tailored verification mechanisms have the following approach in common, which might be of independent interest: Standard verification mechanisms assume that a verifier knows the correct input and receives the output together with a certificate that allows it to check the correctness of the output. An exception are probabilistically checkable proofs, where a verifier can be convinced about the correctness of an output by just seeing a digest of the certificate. We are following a related approach in a

Read the complete text