.png){kind=icon}
.png){kind=icon}
Return
Supervised Distributed Computing
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-031-99872-0_4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 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, omega) is an element of 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, information can be exchanged between the workers, and the workers have access to the source and target, 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 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.
Keywords:
Distributed Computing
Fault Tolerance
Peer-to-peer Networks
Journal
E
IF:
0
Papers:
21
Citations:
0