Supervised Distributed Computing: Efficiency and Robustness under a Majority of Adversarial Workers
arXiv:2605.14784v1 [cs.DC] 14 May 2026
John Augustine, Henning Hillebrandt, Manish Kumar, Christian Scheideler, and Julian Werthmann May 15, 2026
Abstract We consider a recently proposed supervised distributed computing paradigm [3] 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 β ∈ [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 any constant β < 1 while the expected work for the honest workers is close to a 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.
1
Introduction
In the standard master-worker paradigm, there is a master and a collection of workers. The master is responsible for assigning tasks to the workers and collecting their outputs while the workers are supposed to execute the tasks in a correct and timely manner. Countermeasures against workers who do not deliver their outputs in a timely manner are relatively simple: Wait until a timeout has been reached, and then assign the task to another worker. However, checking the correctness of the output is more challenging. A standard approach has been to assign the same task to two workers, and if their outputs disagree, to assign it to a third worker or more until a majority of workers agree on the output. This has turned out to be effective in practice against non-cooperating adversarial workers (e.g., SETI@home [17]), but is not effective if there is a constant fraction of cooperating adversarial workers. Various alternative approaches may be used such as challenging workers with tasks whose correct outputs are already known to identify and blacklist adversarial workers, but in this case, computations performed by honest workers are wasted. Thus, ideally, appropriate verification mechanisms are available that allow the master to check the correctness of an output without consulting other workers. Such verification mechanisms are known for various problems and have been studied in the context of certifying algorithms [19] and interactive proofs [11]. In the 1
maxflow problem, for example, the master may not just expect a maxflow solution from the worker but also a mincut, which must have the same values to be correct due to the famous maxflowmincut theorem. For distributed computations, it can be more challenging to identify lightweight verification mechanisms at the task level, but as was demonstrated in [3], this is possible, for example, for distributed matrix multiplication and sorting. Certainly, requiring the master to perform these verifications puts a significant burden on the master and therefore severely limits the scalability of the master-worker approach. To avoid this problem, the supervised distributed computing paradigm was recently proposed, which shifts the burden of verifying the outputs of task computations to the workers so that the supervisor is not involved in any I/O activities anymore. Instead, the supervisor just focuses on assigning tasks to workers and introducing them to each other to make sure that the computation proceeds in a controlled manner. To ensure that there is a chance for the computation to be performed correctly, a critical assumption of that approach is to assume that the source, which stores the input of the distributed computation, and the target, which is supposed to collect the final outputs of the computation, are reliable. In that case, the input will be delivered correctly to the workers responsible for the initial tasks, and when the target tells the supervisor that all final outputs have been correctly delivered to it, the supervisor knows for sure that the computation was successful. Prior to our work, only efficient supervised distributed computing solutions were known for the case where the fraction of adversarial workers is a sufficiently small constant [3]. In this work, we show that there are supervised approaches that are efficient and robust against any constant fraction of adversarial workers less than 1. Before we state our concrete contributions, we formally introduce the supervised distributed computing paradigm and give an overview of related work.
1.1
Supervised Distributed Computing Paradigm
In the supervised distributed computing paradigm, there are four roles: a supervisor, a source, a target, and a collection of workers. The term supervisor was suggested instead of master to highlight its lightweight scheduling role. The source, target, and supervisor are assumed to be reliable in the sense that they operate on time and are not subject to crashes or adversarial behavior. Given an instance I of a computational problem, I is initially stored in the source, and the supervisor’s goal is to orchestrate the workers so that, in the end, a correct solution S(I) to I is stored in the target. Note that the supervisor, source, and target are abstractions. Depending on the application, these roles may overlap or may be realized by multiple entities. For example, if S(I) is small (e.g., a simple “yes/no” answer), it might be convenient for the supervisor and target to be the same entity. In decentralized environments with a sufficiently small fraction of adversarial peers, a reliable supervisor might be emulated by a quorum of peers, and a source may consist of a collection of repositories with read-only access. We assume that the distributed computation for some instance I can be represented as a directed acyclic task graph G = (V, E) that is known to the supervisor.1 Each node v ∈ V represents a task, and for every edge (u, v) ∈ E, u is called a predecessor of v and v is called a successor of u. We denote the set of successors of a task v in G as succG (v) and the set of predecessors in G as predG (v). For every task v ∈ V , v needs the outputs of all predecessors to be executable. Nodes without incoming edges represent initial tasks; they receive their inputs directly from the source. Nodes without outgoing edges represent final tasks; they are supposed to send their outputs to the target, where the final solution S(I) is assembled. For our analysis, we use n = |V | to denote the number of tasks and D to denote the depth of G, i.e., the length of the longest directed path in the 1
Example task graphs for matrix multiplication and sorting have been presented in [3].
2
graph. Furthermore, for each task v ∈ V , we use D(v) ∈ {1, . . . , D} to denote the depth of v in G, i.e., the length of the longest directed path from an initial task to v. 1.1.1
Worker Sampling and Adversarial Model
We assume that the supervisor has access to a black-box sampling mechanism that, when asked for a worker, returns an adversarial worker with probability at most β ∈ [0, 1), and otherwise an honest worker.2 The sampling mechanism ensures that only available honest workers are picked, and an honest worker only declares itself available if it is not currently busy with a task. The set of workers may change arbitrarily over time, but we assume that there are always (sufficiently many) available honest workers so that the sampling mechanism can work as desired. β is known to the supervisor, but this is not a severe constraint since our solution works efficiently for any constant β < 1, and therefore, the supervisor may assume that β = 0.9, for example. The adversary is omniscient, i.e., it has complete knowledge of the system’s past and present state and can coordinate all adversarial workers. However, it cannot predict the supervisor’s future random choices or the future choices of the sampling mechanism. Honest workers, once selected, are assumed to remain accessible and function correctly for as long as the output of the task assigned to them is needed for the execution of G (which depends on the scheduling strategy of the supervisor). 1.1.2
Task Executions
For simplicity, we assume that the time progresses in synchronous rounds. Each round is sufficiently long to ensure that the following sequence of events can take place: (1) The supervisor samples the desired number of workers for tasks that it wants to get executed in that round, (2) the supervisor introduces workers to each other so that formerly sampled workers can forward their outputs to the corresponding newly sampled workers, (3) the newly sampled workers check whether the received outputs are correct and complete,3 and (4) if so, they may execute the task assigned to them. The assumption of synchronous rounds is reasonable if all tasks require roughly the same computational effort and the time required for receiving outputs and verifying their correctness is negligible compared to executing the task. The most critical issue is coming up with a lightweight verification mechanism for the received outputs, which has been shown to be possible for certain problems and is an active area of research, but here we just assume that such verification mechanisms are available and focus instead on the scheduling part.4 1.1.3
Efficiency and Robustness Goals
We consider a supervised solution to be efficient if the following goals can be met: • The expected communication work of the source is linear in the size of the input I. • The expected communication work of the supervisor is linear in the size of G and independent of the size of the input I and its solution S(I). • The expected communication and verification work of the honest workers is in O(d), where d is a bound on the in- and outdegree of G. 2
For example, the supervisor could be sampling from an infinite pool of workers. Workers can discard any received outputs that do not adhere protocol, including messages that are too large. 4 The assumption is reasonable, in particular due to the existence class NP of problems that are difficult to compute but easy to verify. 3
3
• The expected total computation work of the honest workers is asymptotically equal to the work required for executing all tasks in G. • The expected runtime of the computation, measured in rounds, is asymptotically equal to the depth D of the task graph. • The expected communication work of the target is linear in the size of the solution S(I). These requirements explicitly rule out trivial scheduling strategies. For example, assigning the entire computation to a single worker would result in a runtime of O(|V |), which can be significantly larger than D. Similarly, involving the supervisor in handling the input and output data would make its work dependent on |I| or |S(I)|, which can be much larger than the size of G, thereby creating a bottleneck. We call a supervised solution robust if, despite the presence of adversarial workers, eventually a correct solution can be assembled at the target.
2
Related Work
Although the master-worker paradigm has been around for decades, it is still widely used in practice. Approaches following that paradigm can be found in volunteer-based computing (e.g., PrimeNet and SETI@home) as well as data processing in large computational clusters (e.g., Google’s MapReduce paradigm [10]). While in the basic master-worker paradigm, tasks are typically independent, the MapReduce paradigm can cover situations where a task may spawn several subtasks (the Map operation) whose outputs are collected (via the Reduce operation) to assemble the final output of the task. Starting with the work of Fernandez et al. [12, 13] various algorithmic techniques have been explored for the case that the tasks are independent of each other and the tasks need to be computed by workers that are potentially malicious (e.g., [6, 16]). A standard assumption in these papers is that there is a fixed set of n workers and a set of t tasks, where n ≤ t. The computation proceeds in synchronous rounds. In each round, the master can assign any collection of tasks to the workers, and during a round, each worker can compute only one task from the master and report the result back to it. The goal of the master is to accept only correct answers of every task, w.h.p.5 Techniques that have been explored to achieve that are voting (a majority threshold of workers have to agree on the output), challenges (where tasks with known outputs are given to workers to identify malicious ones), or combinations of these. Appropriate strategies for the master based on these techniques were presented in [6, 16] that, for the case of binary outputs, achieve the stated goal if the probability of malicious or faulty behavior is less than 1/2, and for scenarios where more outputs are allowed, this bound may even be lower. Furthermore, a lower bound of Ω(t log n) for the total work was shown for the case that an f -fraction, 0 < f < 1/2, of the workers may return incorrect results with probability 0 < p < 1/2, while the master does not have a priori knowledge of f and p [16]. Reputation-based (e.g., [7, 22]) and game-theoretical approaches (e.g., [2, 8]) have also been considered in this context, but these are beyond the scope of this paper. In the works above, the master does all the checking. Goodrich [14] investigated a method to prevent cheating that uses the workers to check each others’ outputs. As the main result, he shows that three rounds and a replication factor of 6 suffice to identify all false outputs among t = n tasks, so long as there are at most 5 We say that an event occurs with high probability (w.h.p.), if it occurs with probability at least 1 − n−c for a constant c. 5
4
The supervised distributed computing model considered here was introduced by Augustine, Scheideler and Werthmann [3]. They studied two classes of task graphs: paths (as a warm-up) and arbitrary directed acyclic graphs (DAGs). For the path case, they showed that when β ≤ 1/12, their scheduling approach terminates correctly in a linear number of rounds, w.h.p. Moreover, for any adversarial strategy, the source and target send and receive the solution only a constant number of times in expectation, and the total computational and verification work performed by the workers is within a constant factor of optimal. They then generalized their path strategy to DAGs and showed that as long as β ≤ (1/(2(2d + 1)))2+ϵ , for an arbitrary constant ϵ > 0, where d denotes the maximum indegree of the task graph, the computation finishes within O(D + log n) rounds, w.h.p. Research on verification in adversarial environments can be traced back to the pioneering work of Blum, Evans, Gemmell, Kannan, and Naor [4], who studied how to check the correctness of operations performed on a data structure controlled by an adversary.Their work initiated a significant amount of research on authenticated data structures (see [23] for a survey), which typically involves a trusted source, an untrusted server, and a client. The paradigm of certifying algorithms [1] further explores the separation between computation and verification. In this setting, an algorithm outputs not only a solution but also a witness whose correctness can be efficiently verified by a checker. Certifying algorithms have been developed for a variety of sequential problems, including graph problems and geometric settings (e.g., [19]). There is a large body of work on cryptographic approaches to check the correctness of outputs (see [9] for a survey). This line of work is commonly formalized using interactive proof systems [11], where a powerful prover convinces a weaker verifier of the correctness of a computation. More recent developments include non-interactive arguments such as SNARGs and SNARKs [5, 20], which aim at succinct verification and have found applications in blockchain systems. Supervised distributed computing solutions (ours included) are designed to take advantage of such efficient verification tools to solve large-scale parallel and distributed computing problems in the presence of Byzantine participants.
2.1
Our Contributions
We present a supervised distributed computing solution that can tolerate a β-fraction of adversarial workers for any constant β < 1 and any directed acyclic task graph. This is a significant improvement over the DAG scheduling approach of [3], which only preserves efficiency for β ∈ O((log d)/d2 ), where d is a bound on the maximum in- and outdegree of the task graph G (cf. Section B for the proof). Since honest workers can be a minority, all majority-based solutions will be unhelpful even if we assign a large number of workers per task. Our supervised strategy organizes the task graph into levels and assigns several workers to each task in a pipelined manner, starting at time O(i · log d · log log n) in level i. When a worker is assigned to a task, it first checks the outputs of O(log d · log log n) previously assigned workers of that task, and if it gets the correct output from one of them, it is done. Otherwise, it contacts O(log d · log log n) previously assigned workers of all preceding tasks, and if it gets a correct output from each preceding task, it executes the task assigned to it and is done. Otherwise, it fails. As it turns out, our solution is highly efficient in the sense that each task is executed by only 1 + o(1) honest workers on expectation, and therefore, the total expected number of computations performed by honest workers is n(1 + o(1)), where n is the number of tasks. Moreover, owing to the way the workers are assigned to the tasks, the distributed computation finishes in O(D log d · log log n) rounds, w.h.p. (see Theorem 8). To show that the computation finishes successfully, w.h.p., we use a complex witness argument 5
that is able to identify a significant amount of places where adversarial workers were chosen in the task graph whenever the computation fails. This then allows us to show that the probability for such a witness to be found when using the random sampling mechanism is polynomially small, thereby implying that our solution is correct w.h.p.
3
Handling a Majority of Adversarial Workers
Before we begin describing our algorithm, we remark that [3] shows how to transform any task graph G = (V, E) into a leveled network of the same depth, i.e., a graph where the tasks are divided into levels and edges only connect tasks in adjacent levels. The key idea is to assign each task v ∈ V to level D(v). All edges that connect tasks of non-adjacent levels are then replaced by paths consisting of one additional task for each level in between. Note that this construction only has to be executed once before any distributed computation starts. Therefore, we will w.l.o.g. only consider the case where the task graph is a leveled network. In the following, whenever we refer to a DAG, we will assume that this transformation has already been applied. To motivate our new scheduling approach, we start with a simple straw man algorithm that can handle an arbitrary β-fraction of adversarial workers for any constant β < 1, but comes with significant downsides. Suppose the task graph G = (V, E) is a leveled network of depth D. In each round t = 1, . . . , D, the supervisor assigns γ many workers to each task v ∈ V with D(v) = t and instructs all workers assigned to predecessors of v (or the source if t = 1) to send their output to all workers assigned to v. Every honest worker then verifies all the outputs it received and, if it received at least one correct output for each preceding task, computes the task it was assigned to. If we set γ = Θ(log n), one can prove that every task will be assigned at least one honest worker, w.h.p., which implies that the target will learn the correct output and the computation succeeds. Although this algorithm is time-optimal, every honest worker needs to communicate with Θ(d log n) other workers and needs to perform Θ(d log n) many verifications, where d ≥ max{indeg(G), outdeg(G)} is an upper bound on the degree of the task graph. While Ω(d) is a natural lower bound on the number of verifications and communication required per worker, the logarithmic dependency on n severely limits the algorithm’s performance in practice. Furthermore, each task gets executed by Θ(log n) honest workers in expectation, which wastes computational resources.
3.1
Algorithm Description
We reduce the communication and verification costs of the straw man algorithm by letting each worker send their output only to a small subset of the workers assigned to each succeeding task in the following way. Instead of immediately assigning γ workers to a single task per round, the supervisor assigns only one worker per task per round, but may assign workers to multiple tasks at once. Specifically, the supervisor assigns workers to each task v of depth D(v) between rounds tmin (v) := (D(v) − 1) · δ + 1 and tmax (v) := (D(v) − 1) · δ + γ, where δ ≥ 1 is some fixed parameter that determines the time offset between tasks. Hence, in each round t = 1, . . . , γ + (D − 1) · δ, the supervisor assigns exactly one worker to each task v with t ∈ [tmin (v), tmax (v)]. For every worker w assigned to task v in round t, the supervisor first instructs all workers assigned to task v in rounds t′ ∈ [max{t − 2δ, tmin (v)}, t − 1] to send their output for task v to w. If it is honest, w verifies these outputs one by one until it succeeds in verifying an output or fails to verify all outputs. If it succeeds in verifying an output, it does not need to do any further verifications and no computation, but is required to remain available for 2δ additional rounds to provide v’s output to its successors. Otherwise, w informs the supervisor about its failure to verify. The supervisor then instructs all
6
workers assigned to any preceding task v ′ ∈ predG (v) in rounds t′ ∈ [max{t − 2δ, tmin (v ′ )}, t − 1] to send their output for task v ′ to w. Again, if it is honest, w verifies these outputs one by one until it succeeds for one of them or fails for all of them. If w receives a correct output for each of v’s predecessors, w computes the output of v and remains in the system for 2δ further rounds to provide it to its successors. Otherwise, it failed to compute an output and remains in the system for 2δ rounds to provide an error message to its successors. We present pseudocode for the supervisor in Algorithm 1 and for the workers in Algorithm 2, both located in Section A. With this approach, every honest worker needs to communicate with only Θ(dδ) many other workers and needs to perform only Θ(dδ) many verifications. Furthermore, since workers can forward their output to (some) other workers assigned to the same task, the expected number of task executions by honest workers is reduced. However, the probability that the computation succeeds now depends on δ. We show in the remainder of the section that the algorithm still succeeds with high probability if we set δ = Θ(log1/β (d) · log1/β log n) and γ = Θ(log n).
3.2
Preliminaries for the Analysis
We model the behavior of the algorithm on a task graph G = (V, E) as a worker graph GW = (VW , EW ), in which each node (v, t) ∈ VW represents a worker that was assigned to task v ∈ V in round t and each edge (w, w′ ) ∈ EW represents that worker w might send data to worker w′ . An example of a worker graph is depicted in Figure 1. Definition 1 (Worker Graph). For a task graph G = (V, E), we define the worker graph GW = (VW , EW ). For each task v of depth D(v), VW contains a node (v, t) if the supervisor assigns a worker to v at time t. Specifically, VW = {(v, t) | v ∈ V ∧t ∈ {(D(v)−1)·δ+1, . . . , (D(v)−1)·δ+γ}}. For w, w′ ∈ VW , EW contains an edge from w to w′ if w could send data to w′ after assignment, (1) (2) i.e., EW = EW ∪ EW with (1)
EW = {((v, t), (v ′ , t′ )) ∈ VW × VW | v ′ = v ∧ t′ ∈ {t + 1, . . . , t + 2δ}} and (2)
EW = {((v, t), (v ′ , t′ )) ∈ VW × VW | v ′ ∈ succG (v) ∧ t′ ∈ {t + 1, . . . , t + 2δ}}. We refer to the nodes of GW as workers and call a node (v, t) ∈ VW an initial worker, if v is an initial task of G, and a final worker, if v is a final task of G.
time
time
Figure 1: The worker graph for a task graph with n = 6, γ = 13, and δ = 1. Each column of tasks has a separate time axis. The tasks within a column are offset s.t. workers assigned at the same time are located directly above or below each other.
An execution of the algorithm corresponds to an assignment of workers to the nodes of GW , 7
where each worker is independently malicious with probability β and honest with probability (1−β). We call honest workers that can provide the output for their own task to their successors successful and all other honest workers failed. The algorithm succeeds when there is a successful worker assigned to each final task. Definition 2 (Successful & Failed Workers). For an assignment of honest and malicious workers to tasks, we call an honest worker w = (v, t) ∈ VW successful if for all initial tasks v ′ that are ancestors of v in G, there is a directed path of honest workers connecting an initial worker w′ = (v ′ , t′ ) to w in GW . Otherwise, we call w failed. We begin our analysis by noting that, from the adversarial workers’ perspective, the most effective way to interfere with the computation is simply to avoid ever sending a correct output. Any correct output would only contribute to the computation’s success, which contradicts their objective. Hence, to model the strongest possible adversarial behavior, we will w.l.o.g. restrict our analysis to the case where no malicious worker ever sends a correct output. Observation 3 (Dominant Adversarial Strategy). If the computation succeeds for some assignment of malicious and honest workers, where no malicious worker ever sends a correct output, the computation also succeeds for the same assignment of malicious and honest workers, if there are malicious workers that send some correct outputs. To prove the correctness of the algorithm, we will proceed as follows. First, we show that for every assignment A of honest and malicious workers to the tasks of G that causes the computation to fail, we can identify a certain structure in the worker graph GW , which we call a valid witness sequence with respect to A. We then show that for a random assignment A of workers to tasks, where each worker is independently malicious with probability β and honest with probability (1 − β), it is unlikely that a valid witness sequence w.r.t. A exists. By the contraposition of the first statement, it follows that the computation will succeed with high probability. We now provide a definition of valid witness sequences. To this end, we first define witness sequences, which describe the structure that we will analyze in GW independently of which workers are honest or malicious. Intuitively, a witness sequence W is a sequence of workers that connects the “left side” of GW with the “right side”. More precisely, W consists of contiguous (possibly empty) subsets of workers Mi ⊆ VW assigned to the same task v ∈ V and corresponding workers wi ∈ VW , where wi is the next worker assigned to v after Mi , or wi =⊥ if there is no worker after Mi . Initially, the first subset M1 = {(v, tmin (v)), . . . , (v, t − 1)} contains the first worker of some arbitrary task v ∈ V and continues to the right until some arbitrary worker (v, t − 1). If t − 1 = tmax (v), W reached the last worker of task v. In this case, we set w1 =⊥, which marks the end of the sequence. Otherwise, worker w1 = (v, t) exists, which is added to W . From w1 , the sequence now either moves downwards to a task v ′ ∈ succG (v) or upwards to a task v ′ ∈ predG (v). If the sequence moves downwards, it continues at worker w = (v ′ , t + 1) for some task v ′ ∈ succG (v), by either letting w be the start of the next subset M2 , or letting M2 = ∅ and w2 = w. Note that this is only possible if v is not a final task and t ≥ tmin (v ′ ) − 1, as otherwise w does not exist. If the sequence moves upwards, it continues at worker w = (v ′ , t) directly above w1 for some task v ′ ∈ predG (v). This is only possible if v is not an initial task. If w does not exist because t > tmax (v ′ ), we simply set M2 = ∅ and w2 =⊥, and the sequence ends. The sequence continues in this way until an wi =⊥ is added. Additionally, we associate each upwards movement from some worker wi = (v, t) with a contiguous subset of workers Mi′ assigned to the same task v ′ ∈ predG (v), such that all workers in Mi′ are assigned before time t and Mi′ is disjoint with all other subsets Mj and Mj′ with i ̸= j. 8
Formally, we define a witness sequence as a sequence of triples (Mi , Mi′ , wi ) as follows. An example of a witness sequence is depicted in Figure 2. Definition 4 (Witness Sequence). Let G = (V, E) be a task graph, and GW = (VW , EW ) be ′ the worker graph of G. We call a sequence W = ((M1 , M1′ , w1 ), . . . , (Mℓ , Mℓ′ , wℓ ), (Mℓ+1 , Mℓ+1 = ∅, wℓ+1 =⊥)) with ℓ ≥ 0 a witness sequence, if wi ∈ VW for all 1 ≤ i ≤ ℓ, each Mi ⊆ VW and Mi′ ⊆ VW with 1 ≤ i ≤ ℓ + 1 is a contiguous subsets of workers assigned to the same task, and all of the following properties hold: 1. (v, tmin (v)) ∈ M1 for some v ∈ V . ′ ,w 2. For (Mi , Mi′ , wi ) and (Mi+1 , Mi+1 i+1 ) in W with 1 ≤ i ≤ ℓ − 1 and wi = (v, t), exactly one of the following holds:
• wi+1 = (v ′ , t′ ) with v ′ ∈ succG (v) and t′ > t, and Mi+1 = {(v ′ , t + 1), . . . , (v ′ , t′ − 1)} (possibly empty). Further, Mi′ = ∅. • wi+1 =⊥ and Mi+1 = {(v ′ , t + 1), . . . , (v ′ , tmax (v ′ ))} with v ′ ∈ succG (v). Further Mi′ = ∅. • wi+1 = (v ′ , t′ ) with v ′ ∈ predG (v) and t′ ≥ t, and Mi+1 = {(v ′ , t), . . . , (v ′ , t′ −1)} (possibly empty). Further, t ≥ tmin (v) + δ, and Mi′ := {(v ′ , t′′ ), . . . , (v ′ , min{t′′ + 2δ − 1, tmax (v ′ )})} for a t′′ ≤ t − 2δ. • wi+1 =⊥ and Mi+1 = {(v ′ , t), . . . , (v ′ , tmax (v ′ ))} with v ′ ∈ predG (v) (possibly empty). Further, t ≥ tmin (v) + δ, and Mi′ := {(v ′ , t′′ ), . . . , (v ′ , min{t′′ + 2δ − 1, tmax (v ′ )})} for a t′′ ≤ t − 2δ. ′ are pairwise disjoint. 3. The sets M1 , . . . , Mℓ+1 , M1′ , . . . , Mℓ+1
4. Exactly one of the following holds: • (v, tmax (v)) ∈ Mℓ+1 for some v ∈ V . • ℓ ≥ 1, wℓ ∈ {(v, tmax (v) − δ + 1), . . . , (v, tmax (v))} for some v ∈ V and Mℓ+1 = ∅. ′ , H Further, we denote MW := M1 ∪ · · · ∪ Mℓ+1 , M′W := M1′ ∪ · · · ∪ Mℓ+1 W := {wi | 1 ≤ i ≤ ℓ}, ′ and FW := {wi = (v, t) | 1 ≤ i ≤ ℓ ∧ Mi+1 ∪ {wi+1 } contains no (v , t′ ) with v ′ ∈ succG (v)}. If the witness sequence we refer to is obvious from the context, we omit the subscripts.
We now define what it means for a witness sequence to be valid with respect to an assignment of workers to tasks. For a witness sequence W to be valid, we require for each triple (Mi , Mi′ , wi ) in W , that all workers in Mi and Mi′ are malicious and that wi is honest. Moreover, if W continues upwards, wi must be a failed worker, whereas if W continues downwards, wi must be a successful worker. An example of a witness sequence that is valid w.r.t an assignment is depicted in Figure 3. Definition 5 (Validity w.r.t an Assignment). For a task graph G = (V, E) and its worker graph GW = (VW , EW ), let A be an assignment of workers to tasks. We call a witness sequence W = ((M1 , M1′ , w1 ), . . . , (Mℓ , Mℓ′ , wℓ ), (Mℓ+1 , ∅, ⊥)) valid w.r.t. A, if all workers in M ∪ M′ are malicious, all workers in F are honest workers that failed and all workers in H \ F are honest workers that were successful. With these definitions in place, we are ready to prove the correctness of the algorithm. The first step is to prove that a failing execution of the algorithm implies the existence of a valid witness sequence. In Section 3.3, we provide intuition for the more general statement for DAGs by proving the following lemma stating that a valid witness sequence must exist when the computation fails, if the task graph is a path graph. 9
time
time
Figure 2: An example of a witness sequence starting from the top right task and ending at the top left task. Consecutive triples in the witness sequence are connected by a dashed line. For each triple (M, M ′ , w), w is enclosed by a circle, the workers of M are enclosed by a box adjacent to w, and the workers of M ′ are enclosed by a box at the next task visited by the witness sequence. w is connected to both M and M ′ by a solid line. wℓ+1 =⊥ is not depicted.
time
time
Figure 3: A witness sequence that is valid w.r.t. to an assignment A. To depict A, successful workers are presented in green color, failed workers are presented in yellow, and malicious workers are presented in red. For each triple (M, M ′ , w), M and M ′ contain only malicious workers, and w is an honest worker that is either successful if the sequence continues at a succeeding task or failed if the sequence continues at a preceding task.
Lemma 6 (Valid Witness Sequence Existence). For a path graph G = (V, E) with V = {v1 , . . . , vn } and its worker graph GW = (VW , EW ), we consider an assignment A of workers to tasks which caused the computation to fail. Then, the construction in Theorem 10 terminates and constructs a witness sequence that is valid w.r.t. A. Afterwards, in Section 3.4, we prove the statement for any DAG formulated in the following lemma. Lemma 7 (Valid Witness Sequence Existence). For a task graph G = (V, E) and its worker graph GW = (VW , EW ), we consider an assignment A of workers to tasks which caused the computation to fail. Then, there is a witness sequence in GW that is valid w.r.t. A. Finally, in Section 3.5 we conclude the analysis of the correctness by proving that it is unlikely for a valid witness sequence to exist. Additionally, we provide a bound on the work performed by the workers and prove the main theorem of this paper stated in the following. 10
Theorem 8. Let G be a task graph and β < 1 be any fixed value representing the fraction of adversarial workers. For δ = Θ(log1/β (d)·log1/β log n) and γ = Θ(log n), the target learns the correct solution w.h.p., and the algorithm terminates within O(D log1/β (d) · log1/β log n + log n) rounds. Each honest worker performs at most one computation for each time it was assigned, O(d log1/β (d) · log1/β log n) verifications, and O(d log1/β (d) · log1/β log n) communication. In expectation, each task gets executed by 1 + o(1) honest workers and the total number of computations performed by honest workers is n(1 + o(1)). The source needs to send the input O(log n) times for each initial task of G, the target needs to receive and verify the output O(log n) times for each final task of G, and the supervisor performs O(n log n) assignments and O(nd log(n) · log1/β (d) · log1/β log n) introductions.
3.3
Witness Existence for the Path Case
Let G = (V, E) be a directed path with n nodes v1 , . . . , vn , where v1 is the initial task and vn is the final task, and let GW = (VW , EW ) be the worker graph of G. Before we show how to construct a valid witness sequence in GW , we prove three simple properties that we require for the construction to be well-defined. Lemma 9 (Properties of Assignments). Let G = (V, E) be a path graph with V = {v1 , . . . , vn } and let GW = (VW , EW ) be its worker graph. For an assignment A of workers to tasks, the following holds: • If there is no task for which all assigned workers are malicious, there is a task v where the first honest worker assigned to v is successful. • If a worker (vk , t) failed, the task vk−1 exists. • If A caused the computation to fail and a worker (vk , t) is successful, the task vk+1 exists. Proof. If there is no task for which all assigned workers are malicious, task v1 is assigned at least one honest worker. Since v1 is an initial task, all honest workers assigned to v1 receive their input from the source and are thus successful. In particular, the first honest worker assigned to v1 is successful. Therefore, there is a task v, where the first honest worker assigned to v is successful. Next, consider a worker (vk , t) that failed. Since all honest workers of task v1 are successful, we have 1 < k ≤ n. Hence, task vk−1 exists. Finally, if A caused the computation to fail, there is a task for which no assigned worker is successful as the target would have otherwise received the output. Let vj be the first such task, i.e., no task in {vj , . . . , vn } is assigned a worker that is successful. Hence, for all successful workers (vk , t), we have 1 ≤ k < j ≤ n and the task vk+1 exists. Definition 10 (Valid Witness Sequence Construction for Path Graphs). For a path graph G = (V, E) with V = {v1 , . . . , vn } and its worker graph GW = (VW , EW ), we consider an assignment of workers to tasks which caused the computation to fail. We construct a valid witness sequence W by iteratively adding triples (M, M ′ , w) ∈ P(VW ) × P(VW ) × VW to W until a triple (M, ∅, ⊥) is added that marks the end of the construction. If there is a task v ∈ V such that all workers assigned to v are malicious, we add the triple (M1 , ∅, ⊥) to W with M1 = {(v, tmin (v)), . . . , (v, tmax (v))}. Otherwise, we consider the last task v, where the first honest worker (v, t) assigned to v is successful (which exists due to Theorem 9), and add (M1 , ∅, (v, t)) to W with M1 = {(v, tmin (v)), . . . , (v, t − 1)}. After adding (Mi , Mi′ , wi ) to W , if ′ ,w wi =⊥ our construction terminates. Otherwise, if wi = (vk , t) ∈ VW we add (Mi+1 , Mi+1 i+1 ) to W . To define Mi+1 and wi+1 , we distinguish two cases:
11
1. wi is successful. Then vk+1 exists due to Theorem 9. (a) If t + 1 < tmin (vk+1 ), we empty W and restart the construction (setting i := 0). We set w1 = (vk+1 , t′ ) to be the first honest worker assigned to task vk+1 and M1 = {(vk+1 , tmin (vk+1 )), . . . , (vk+1 , t′ − 1)} (possibly empty). (b) Otherwise, if there is no honest worker in M := {(vk+1 , t + 1), . . . , (vk+1 , tmax (vk+1 ))}, we set Mi+1 = M and wi+1 =⊥. (c) Otherwise, we set wi+1 = (vk+1 , t′ ) to be the first honest worker in M (of (b)) and Mi+1 = {(vk+1 , t + 1), . . . , (vk+1 , t′ − 1)} (possibly empty). 2. wi failed. Then vk−1 exists due to Theorem 9. (a) If t > tmax (vk−1 ), we set Mi+1 = ∅ and wi+1 =⊥. (b) Otherwise, if there is no honest worker in M := {(vk−1 , t), . . . , (vk−1 , tmax (vk−1 ))}, we set Mi+1 = M and wi+1 =⊥. (c) Otherwise, we set wi+1 = (vk−1 , t′ ) to be the first honest worker in M (of (b)) and Mi+1 = {(vk−1 , t), . . . , (vk−1 , t′ − 1)} (possibly empty). ′ Additionally, if wi+1 =⊥ or wi+1 is successful, we define Mi+1 = ∅, and if wi+1 = (vk′ , t′ ) failed, ′ we define Mi+1 = {(vk′ −1 , t′′ ), . . . , (v ′ , min{t′′ + 2δ − 1, tmax (vk′ −1 )})}, where (vk′ −1 , t′′ − 1) is the last successful worker assigned to vk′ −1 with t′′ − 1 < t′ (which exists due to Theorem 13).
Note that whenever an honest worker wi+1 is added in the construction above, it was assigned after or at the same time wi was assigned. We formulate this fact in the following observation. Observation 11 (Non-decreasing wi ). For a task graph G = (V, E) and its worker graph GW = (VW , EW ), we consider an assignment of workers to tasks which caused the computation to fail. Let W = ((M1 , M1′ , w1 ), (M2 , M2′ , w2 ), . . . ) be a sequence constructed by Theorem 10. For each 1 ≤ i < j ≤ ℓ with wi = (v, ti ) and wj = (v ′ , tj ), we have ti ≤ tj . Additionally, for each worker wi = (v, ti ), no worker in Mi was assigned before time ti and all workers in Mi′ were assigned before time ti . For the construction in Theorem 10 to be well-defined, we still need to argue that whenever we move upwards from a failed worker wi = (vk , t), there is indeed a successful worker assigned to task vk−1 before time t. In fact, we can show something even stronger. Whenever we add an honest worker wi = (vk , t) to W , there is a successful worker that was assigned before time t for every task vj with 1 ≤ j < k. Moreover, if wj′′ = (vj , t′′ − 1) is the last successful worker assigned to task vj before time t, there is no failed worker (vj+1 , t′ ) in W with t′′ − 1 < t′ < t. In other words, no worker wj′′ has been “used” before by some other failed worker wi′ in W to define its own set Mi′′ ′′ } the success barrier for w . An example of a success barrier for any i′ < i. We call {w1′′ , . . . , wk−1 i is depicted in Figure 4. The existence of a success barrier will be crucial later to argue that all of the sets Mi′ created by the construction are disjoint. We now formally define the success barrier and prove that every honest worker added to W indeed has one. Definition 12 (Success Barrier). For a path graph G = (V, E) with V = {v1 , . . . , vn } and its worker graph GW = (VW , EW ), we consider an assignment of workers to tasks which caused the computation to fail. Let W be the sequence constructed by Theorem 10. We call a successful worker w′′ = (vk , t′′ − 1) linked at time t if there is a failed worker w′ = (vk+1 , t′ ) in W such that t′′ − 1 < t′ < t. 12
Let (M, M ′ , w) be a triple we add to W (cf. Theorem 10) with w = (vk , t). If for all 1 ≤ j < k, there is a successful worker assigned to task vj before time t and the last such worker wj′′ is not ′′ } the success barrier for w. linked at time t, we call {w1′′ , . . . , wk−1 v1 v2 v3 v4 v5 v6 v7 time Figure 4: An example of the success barrier for a path graph with 7 nodes, where γ = 20 and δ = 1. The green line connects the nodes in the success barrier for the first failed worker in the witness sequence. We can link each failed worker with a unique honest node in its success barrier and assigned to the preceding task. This honest worker must be succeeded by 2δ = 2 malicious workers that are not in the witness sequence, which compose the set M ′ corresponding to that failed worker.
Lemma 13 (Success Barrier Existence). For a path graph G = (V, E) with V = {v1 , . . . , vn } and its worker graph GW = (VW , EW ), we consider an assignment of workers to tasks which caused the computation to fail. Let W = ((M1 , M1′ , w1 ), (M2 , M2′ , w2 ), . . . ) be the sequence constructed by Theorem 10. Then, for all i ≥ 1 with wi ̸=⊥, there is a success barrier for wi . Proof. We prove the statement inductively. We start by proving that there is a success barrier for w1 = (vk , t1 ). If w1 is successful, there must be a directed path P = ((v1 , t′1 ), . . . , (vk−1 , t′k−1 )) of length k − 1 with (vk−1 , t′k−1 ) ∈ predGW (w1 ) s.t. P consists only of successful workers and connects w1 to an initial worker (v1 , t′1 ). The topology of the worker graph yields, that t′1 < · · · < t′k−1 < t1 . Thus, there exists a successful worker (vj , tj ) assigned before time t1 for each 1 ≤ j < k. The existence of a last successful worker wj′′ assigned to vj before time t1 immediately follows. As W only contains (M1 , M1′ , w1 ) at this point, it does not contain any failed workers. Therefore, the wj′′ ′′ }. If w failed, are not linked at time t, and the success barrier for w1 is given by {w1′′ , . . . , wk−1 1 we must be in a case where we just emptied W (cf. Theorem 10 Case (1a)) as we pick the first starting point of the witness structure such that w1 is successful. From Case (1a), we know that there is a successful worker w assigned before time t1 at task vk−1 . This successful worker again implies the existence of a path of length k − 1 of successful workers connecting w to the initial task. As W only contains (M1 , M1′ , w1 ) at this point, we can argue analogously to the case where w1 is successful that the success barrier for w1 exists. We now fix some i ≥ 1 and prove that the existence of the success barrier for wi = (vk , ti ) implies the existence of the success barrier for wi+1 . Due to the existence of the success barrier of wi , we know that there is a successful worker assigned to all tasks vj before time ti ≤ ti+1 with 1 ≤ j < k that is not linked at time ti . If wi failed, we have wi+1 = (vk−1 , ti+1 ), and the existence of a successful worker assigned to task vj before time ti+1 directly follows for all 1 ≤ j < k − 1. In particular, there are also last successful workers wj′′ = (vj , t′′j − 1) assigned before time ti+1 for all 1 ≤ j < k − 1. Further, by Theorem 11, there can be no failed workers in W that are assigned 13
between times ti and ti+1 . It follows that no wj′′ is linked at time ti+1 . Similarly, if wi is successful, we have wi+1 = (vk+1 , ti+1 ), ti+1 > ti , and wi itself is a successful node located at task vk , again yielding the existence of a successful worker assigned to task vj before time ti+1 for all 1 ≤ j < k +1. As before, this implies that there are also last successful workers wj′′ = (vj , t′′j − 1) assigned before time ti+1 for all 1 ≤ j < k + 1. Further, by Theorem 11, wi itself is not linked at time ti+1 . It again follows that no wj′′ is linked at time ti+1 . We conclude that there is a success barrier for wi+1 . We are now ready to prove that the sequence constructed by Theorem 10 is a valid witness sequence w.r.t. the assignment that caused the execution to fail. To this end, we show that the construction always terminates and that the constructed sequence satisfies Theorems 4 and 5. Proof of Theorem 6. If there is a task v ∈ V such that all workers assigned to task v are malicious, the construction immediately terminates with W = ((M1 , ∅, ⊥)) and M1 = {(v, 1), . . . , (v, γ)}, which is a witness sequence. Further, M = M1 contains only malicious workers, M′ = ∅ and H = ∅. Thus, W is also valid w.r.t. A. Otherwise, note that by Theorem 11, the assignment times of the honest workers in the witness sequence are non-decreasing. Notably, in all cases of Theorem 10 except Case (2c) the assignment times are increasing. Let (Mi , Mi′ , wi ) with wi = (vk , t) be a triple added to the sequence in Case (2c). By construction, we have wi−1 = (vk+1 , t′ ) for t′ ≤ t. Therefore Case (2c) can occur no more than n − 1 times in a row and the construction must eventually terminate. For a triple (Mi , Mi′ , wi ) added by the construction, Mi and wi exactly match the structural requirements of a witness sequence in Theorem 4. Further, all workers in Mi are clearly malicious and wi is an honest worker that failed if wi ∈ FW and was successful if wi ∈ H \ F, i.e. Mi and wi satisfy the requirements of a valid witness sequence w.r.t. A in Theorem 5. It remains to prove that Mi′ also matches Theorems 4 and 5. If wi is successful, we set Mi′ = ∅, which matches the requirements. On the other hand, if wi failed, we need to prove several properties. Let wi = (vk , t). By Theorem 13, there is a last successful worker w′′ = (vk−1 , t′′ − 1) with t′′ − 1 < t. Thus, the set Mi′ = {(vk−1 , t′′ ), . . . , (vk−1 , min{t′′ + 2δ − 1, tmax (vk−1 )})} is well-defined. First, we show that indeed t′′ ≤ t − 2δ and t ≥ tmin (vk ) + δ hold, and that all workers in Mi′ are malicious. Then, we prove that Mi′ ∩ Mj′ = ∅ for all 1 ≤ j ≤ ℓ with j ̸= i, and that Mi′ ∩ Mj = ∅ for all 1 ≤ j ≤ ℓ + 1. First, assume for contradiction that t′′ > t − 2δ. Then, wi ∈ succGW (w′′ ) which contradicts that wi failed. Thus, t′′ ≤ t − 2δ has to hold. Further, since t′′ − 1 ≥ tmin (vk−1 ) = tmin (vk ) − δ, we get that t ≥ t′′ + 2δ > tmin (vk ) + δ. Next, note that there can be no failed workers in Mi′ , as Mi′ ⊆ succGW (w′′ ). Additionally, since t′′ ≤ t − 2δ, all workers in Mi′ were assigned before time t. Hence, there can be no successful worker in Mi′ , as otherwise w′′ would not be the last successful worker assigned to vk−1 before time t. We get that Mi′ contains only malicious workers. Next, let wj = (v ′ , t′ ) with j ̸= i be a different failed worker in W (if there is more than one). ′ If v ̸= vk , we immediately get Mi′ ∩ Mj′ = ∅ because Mi′ and Mj′ belong to different tasks. Thus, consider the case that v ′ = vk . If t′ ≤ t′′ , we get Mi′ ∩ Mj′ = ∅ because all workers in Mj′ were assigned before time t′ . Otherwise, if t′ > t′′ , assume for contradiction that Mi′ ∩ Mj′ ̸= ∅. Since both Mi′ and Mj′ consist of only malicious workers and directly follow the last successful worker assigned to task vk−1 before time t and t′ , respectively, we have Mi′ = Mj′ and w′′ is this last successful worker for both wi and wj . But then, w′′ is linked at either time t or time t′ , which contradicts that w′′ is not linked by Theorem 13. We conclude that Mi′ ∩ Mj′ = ∅ has to hold. Finally, consider some Mj with 1 ≤ j ≤ ℓ + 1. If j = i, we immediately get Mi′ ∩ Mj = ∅ as Mi and Mi′ belong to different tasks. If j > i, note that no worker in Mj was assigned before time t by Theorem 11. As all workers in Mi′ were assigned before time t, we get Mi′ ∩ Mj = ∅. Lastly, if j < i, assume for contradiction that Mi′ ∩ Mj ̸= ∅. Since Mi′ contains only malicious workers and Mj is 14
followed by an honest worker wj = (vk−1 , t′ ), we get that t′ > t′′ has to hold. To connect wj with wi in the sequence, there needs to be a successful worker assigned to task vk−1 that was assigned between times t′′ and t, because our construction only moves downwards when a successful worker is encountered and the assignment times of the honest workers are non-decreasing by Theorem 11. But then, w′′ would not be last successful worker assigned to task vk−1 before time t, which is a contradiction. We conclude that Mi′ ∩ Mj = ∅ has to hold.
3.4
Witness Existence for the DAG Case
We now examine the more general setting in which the task graph G = (V, E) is a DAG. As before, we begin by proving a few simple properties that will help us in arguing that the construction is well-defined. Lemma 14 (Properties of Assignments in DAGs). Let G = (V, E) be a task graph and let GW = (VW , EW ) be its worker graph. For an assignment A of workers to tasks, the following holds: • If there is no task for which all assigned workers are malicious, the first honest worker assigned to any initial task is successful. • If a worker (v, t) failed, the set predG (v) is non-empty and (v, t) failed to receive v’s input corresponding to at least one task in predG (v). • If A caused the computation to fail, there is a task where no assigned worker is successful. Proof. If there is no task for which all assigned workers are malicious, each initial task is assigned at least one honest worker. All honest workers assigned to an initial task receive their input from the source and are thus successful. In particular, the first honest worker assigned to any initial task is successful. Next, consider a worker (v, t) that failed. Since all honest workers assigned to any initial task are successful, we have D(v) = k for 1 < k ≤ n. Hence, predG (v) is non-empty. For (v, t) to have failed, it can not have received all of its inputs, i.e., there is a task in predG (v) that (v, t) did not receive its input from. Finally, assume for contradiction that every task is assigned a worker that is successful. Then, the target receives the output of each final task. This contradicts A causing the computation to fail. To extend our construction from Theorem 10 to the DAG case, we need to generalize the way we find a starting task for the construction, and the way we decide which predecessor and successor to move to. To this end, we need to keep track of how we traverse the DAG. To achieve this, we will employ a stack S. Whenever we leave a task v moving upwards to a predecessor of v, we push task v onto S. Whenever we decide which successor to move downwards to, we pop the top element of S and move to that task. Definition 15 (Valid Witness Sequence Construction for DAGs). For a task graph G = (V, E) that is a DAG and its worker graph GW = (VW , EW ), we consider a failed execution of the algorithm on G. Our construction again iteratively adds elements (M, M ′ , w) ∈ P(VW ) × P(VW ) × VW to W , such that M and M ′ are sets of malicious workers, and w is an honest worker, until a final element (M, ∅, ⊥) is added. If there is a task v ∈ V such that all workers assigned to v are malicious, we again add the triple (M1 , ∅, ⊥) to W with M1 = {(v, tmin (v)), . . . , (v, tmax (v))} and end the construction. Otherwise, we employ a stack S that we initialize to be empty and generalize the witness sequence for paths in the following way:
15
• To identify the starting task, we first consider the task vfail ∈ V of smallest depth for which no assigned worker is successful (ties broken arbitrarily; such a worker exists, cf. Theorem 14). Each task of smaller depth than D(vfail ) must have been assigned at least one successful worker. Starting with v ← vfail , we iteratively move upwards in G until we reach a task whose first worker is successful (which has to exist, cf. Theorem 14). If v’s first honest worker (v, t) failed, we move towards the predecessor v ′ of v, whose first successful worker was assigned last, i.e. v ′ = arg maxvi ∈predG (v) ti (ties broken arbitrarily), where (vi , ti ) is the first successful worker assigned to v’s predecessor vi ∈ predG (v). Afterwards, we perform S.push(v) and set v ← v ′ . Once v’s first honest worker (v, t) is successful, we add (M1 , ∅, (v, t)) to W with M1 = {(v, tmin (v)), . . . , (v, t − 1)}. • After adding an element (Mi , Mi′ , wi ) to W , if wi =⊥, our construction terminates. Other′ ,w wise, if wi = (v, t), we add (Mi+1 , Mi+1 i+1 ) to W . To define Mi+1 and wi+1 we distinguish two cases: 1. If wi is successful, we perform v ′ ← S.pop(). v ′ is a successor of v due to Theorem 16. We continue on v ′ as in Case (1) of Theorem 10. 2. If wi failed, let v ′ ∈ predG (v) be an arbitrary preceding task from which w received no correct output (such a task exists due to Theorem 14). We perform S.push(v) and continue on v ′ as in Case (2) of Theorem 10. ′ Additionally, if wi+1 =⊥ or wi+1 is successful, we define Mi+1 = ∅, and if wi+1 = (v, t′ ) ′ ′′ ′′ ′′ ′′ ′′ failed, we define Mi+1 = {(v , t ), . . . , (v , min{t + 2δ − 1, tmax (v )})}, where v ′′ ∈ predG (v) is an arbitrary preceding task from which wi+1 received no output, and (v ′′ , t′′ − 1) is the last successful worker assigned to v ′′ with t′′ − 1 < t′ (which exists due to Theorem 18).
Note that Theorem 11 extends to the DAG case. Thus, we will still reference it in the following analysis. Next, we argue that whenever we enter Case (1) of Theorem 15, the task on top of the stack S will be a successor of the task we are currently at. Hence, we still move downwards in the DAG and it makes sense to continue as in Case (1) of the path case construction in Theorem 10. Lemma 16 (Construction Well-Defined). When we encounter a worker wi = (v, t) that is successful (Case (1) of Theorem 15) there is a successor v ′ of v on top of S. Proof. We consider the top element of the stack when we enter a task v ∈ V during the construction. Note that entering v from a predecessor requires v to already have been on the stack (it got popped in Case (1) of Theorem 15). Thus, the first time we enter v, we enter from a successor v ′ of v (including while searching for the starting task), which pushes v ′ on top of the stack. Hence, whenever we enter v from a predecessor v ′′ of v, we must have visited v before. Since we must have removed all elements we pushed to the stack since last visiting v, we conclude that some successor v ′ of v must be on top of the stack. We now generalize the concept of the success barrier for DAGs. We say an honest worker w = (v, t) has a success barrier, if for every ancestor v ′′ of v in G there is a successful worker assigned to v before time t. Moreover, if w′′ = (v ′′ , t′′ − 1) is the last successful worker assigned to ancestor v ′′ before time t, there should be no failed worker w′ = (v ′ , t′ ) in W with v ′ ∈ succG (v ′′ ) and t′′ − 1 < t′ < t, such that the sequence moved upwards from v ′ to v ′′ after encountering w′ . As in the path case, this implies that w′′ has not been “used” before by some other failed worker wi′ in W to define its own set Mi′′ for any i′ < i. We formally define the success barrier for DAGs as follows. 16
Definition 17 (Success Barrier for DAGs). For a task graph G = (V, E) and its worker graph GW = (VW , EW ), we consider an assignment of workers to tasks which caused the computation to fail. Let W be the witness sequence constructed by Theorem 15. We call a successful worker w′′ = (v ′′ , t′′ − 1) linked at time t if there is a failed worker wi = (v ′ , t′ ) in W such that v ′ ∈ succG (v ′′ ), t′′ − 1 < t′ < t and wi+1 is assigned to task v ′′ . Let (M, M ′ , w) be a triple we add to W (cf. Theorem 15) with w = (v, t). If for all ancestors v ′ of v in G there is a successful worker assigned to task v ′ before time t and the last such worker wv′ is not linked at time t, we call {wv′ | v ′ ancestor of v} the success barrier for w.
time
time
Figure 5: An example of the success barrier for a DAG, where γ = 13 and δ = 1. The green line connects the nodes in the success barrier for the first failed worker in the witness sequence. We can link each failed worker with a unique honest node in its success barrier and assigned to a preceding task. This honest worker must be succeeded by 2δ = 2 malicious workers that are not in the witness sequence, which compose the set M ′ corresponding to that failed worker.
Lemma 18 (Success Barrier Existence for DAGs). For a task graph G = (V, E) and its worker graph GW = (VW , EW ), we consider an assignment of workers to tasks which caused the computation to fail. Let W = ((M1 , M1′ , w1 ), (M2 , M2′ , w2 ), . . . ) be the sequence constructed by Theorem 15. Then, for all i ≥ 1 with wi ̸=⊥, there is a success barrier for wi . Proof. We prove the statement inductively. We start by proving that there is a success barrier for w1 = (v1 , t1 ). If w1 is successful, consider an arbitrary path (v1′ , . . . , vℓ′ = v1 ) in G from an initial task v1′ to v1 . Analogous to the path case, we can argue that there must be a directed path of ′ ′ successful workers P = ((v1′ , t′1 ), . . . , (vℓ−1 , t′ℓ−1 )) in GW such that (vℓ−1 , t′ℓ−1 ) ∈ predGW (w1 ) and t′1 < · · · < t′ℓ−1 < t1 , as otherwise w1 would not be successful (cf. Theorem 13). Hence, since all ancestors of v lie on some path from an initial task to v, there exists a successful worker assigned before time t1 for each ancestor of v. As W only contains (M1 , w1 ) at this point, it does not contain any failed workers. Therefore, no successful worker is linked at time t1 and the success barrier for w1 exists. If w1 failed, we must be in a case where we just emptied W (cf. Theorem 10 Case (1a)), as we pick the first starting point of the witness structure such that w1 is successful. From Case (1a), we know that there is a successful worker w assigned before time t1 at some preceding task v ∈ predG (v1 ). This successful worker again implies that for every ancestor of v there exists a successful worker assigned before time t1 . However, note that v1 might have some ancestors that are no ancestors of v. We now argue that these ancestors also have such a successful worker. As the assignment times of the honest workers previously added to the sequence were non-decreasing by Theorem 11, we know that task v1 was not visited by the witness sequence before. Since we only 17
go downwards to tasks that are in the stack S, and only add tasks to S after the witness sequence has visited them (once the starting task has been fixed), this implies that v1 belongs to the tasks that were added to S while determining the (original) starting task of the construction. As v1 was on top of S when the witness sequence was at task v, we must have gone up from task v1 to v while determining the starting task. Therefore, v is the predecessor of v1 whose first successful worker was assigned last. As there is a successful worker assigned to v before time t1 , this implies that for all other predecessors of v1 there is also successful worker assigned before time t1 . As before, this also implies that for every ancestor of v1 there is a successful worker assigned before time t1 . As W only contains (M1 , M1′ , w1 ) at this point, we can argue analogously to the case where w1 is successful that the success barrier for w1 exists. We now fix some i ≥ 1 and prove that the existence of the success barrier for wi = (vi , ti ) implies the existence of the success barrier for wi+1 = (vi+1 , ti+1 ). Due to the existence of the success barrier of wi , we know that for each ancestor v ′ of vi there is a last successful worker assigned to v ′ before time ti that is not linked at time ti . From Theorem 11, we have ti+1 ≥ ti , which implies that for each ancestor of vi there is also a successful worker assigned before time ti+1 . Further, there can be no failed worker in W strictly between times ti and ti+1 . Hence, it still holds that for each ancestor v ′ of vi the last successful worker assigned to v ′ before time ti+1 is not linked at time ti+1 . If wi failed, we have vi+1 ∈ predG (vi ) and, thus, every ancestor of vi is also an ancestor of vi+1 . Therefore, it immediately follows that there is a success barrier for wi+1 . If wi is successful, we have vi+1 ∈ succG (vi ), ti+1 > ti , and wi itself is a successful node that is not linked at time ti+1 . Hence, for vi and all ancestors v ′ of vi , there is a last successful worker assigned before time ti+1 that is not linked at time ti+1 . However, vi+1 might have some ancestors that are no ancestors of vi . To analyze these, we distinguish two cases. First, consider the case that W has not visited task vi+1 before, i.e. there is no honest worker (vj , tj ) in W with j < i and vj = vi+1 . Then, we can argue analogously to the base case where w1 failed, that both vi and vi+1 belong to the tasks that were added to S while determining the starting task of the construction, and thus, for every ancestor of vi+1 there is a successful worker assigned before time ti+1 . Further, note that whenever W moves upwards from a task v, it only traverses ancestors of v until it reaches v again. Therefore, as the ancestors of vi+1 that are no ancestors of vi were not added to S while determining the starting task of the construction, they have never been visited by W before. In particular, at the time that wi+1 is added to W , there is no failed worker in W for all ancestors of vi+1 that are no ancestors of vi , i.e. no successful worker of these tasks is linked at time ti+1 . We conclude that there is a success barrier for wi+1 . Next, consider the case that W has visited task vi+1 before. To this end, let wj = (vj , tj ) be the last honest worker in W with j < i and vj = vi+1 . By the induction hypothesis we know that every ancestor v ′ of vj has a last successful worker assigned to v ′ before time tj that is not linked at time tj . Since vj = vi+1 and tj < ti+1 , it follows that also for every ancestor of vi+1 there is a successful worker assigned before time ti+1 . Further, note that since vi+1 was on top of the stack S after wi was added to W , we have vj+1 ∈ predG (vj ). Therefore, vj+1 = vi has to hold, as otherwise wj would not be the last honest worker in W assigned to task vi+1 before wi+1 . Therefore, at the time that wi+1 is added to W , the last successful worker assigned before time ti+1 is still not linked for all ancestors of vi+1 that are no ancestors of vi . We conclude that there is a success barrier for wi+1 . Finally, we prove that the construction in Theorem 15 indeed produces a valid witness sequence. Given the existence of the success barrier, the proof is very similar to the one of Theorem 6 in the path case. For the sake of completeness, we repeat the arguments here anyways. 18
Proof of Theorem 7. If there is a task v ∈ V such that all workers assigned to task v are malicious, the construction immediately terminates with W = ((M1 , ∅, ⊥)) and M1 = {(v, 1), . . . , (v, γ)}, which is a witness sequence. Further, M = M1 contains only malicious workers, M′ = ∅ and H = ∅. Thus, W is also valid w.r.t. A. Otherwise, note that by Theorem 11, the assignment times of the honest workers in the witness sequence are non-decreasing. Notably, in all cases of Theorem 10 (which is referred to by Theorem 15) except Case (2c) the assignment times are increasing. Let (Mi , Mi′ , wi ) with wi = (v, t) be a triple added to the sequence in Case (2c). By construction, we have wi−1 = (v ′ , t′ ) for v ′ ∈ predG (v) t′ ≤ t. Therefore Case (2c) can occur no more than D − 1 times in a row and the construction must eventually terminate. For a triple (Mi , Mi′ , wi ) added by the construction, Mi and wi exactly match the structural requirements of a witness sequence in Theorem 4. Further, all workers in Mi are clearly malicious and wi is an honest worker that failed if wi ∈ FW and was successful if wi ∈ H \ F , i.e. Mi and wi satisfy the requirements of a valid witness sequence w.r.t. A in Theorem 5. It remains to prove that Mi′ also matches Theorem 4 and Theorem 5. If wi is successful, we set Mi′ = ∅, which matches the requirements. On the other hand, if wi failed, we need to prove several properties. Let wi = (v, t). By Theorem 13, there is a last successful worker wv′′ = (v ′′ , t′′ − 1) s.t. v ′ ∈ predG (v) is the arbitrary preceding task we picked for Mi′ (cf. Theorem 15) and t′′ − 1 < t. Thus, the set Mi′ = {(v ′′ , t′′ ), . . . , (v ′′ , min{t′′ + 2δ − 1, tmax (v ′′ )})} is well-defined. First, we show that indeed t′′ ≤ t − 2δ and t ≥ tmin (v) + δ hold, and that all workers in Mi′ are malicious. Then, we prove that Mi′ ∩ Mj′ = ∅ for all 1 ≤ j ≤ ℓ with j ̸= i, and that Mi′ ∩ Mj = ∅ for all 1 ≤ j ≤ ℓ + 1. First, assume for contradiction that t′′ > t − 2δ. Then, wi ∈ succGW (w′′ ) which contradicts that wi failed. Thus, t′′ ≤ t − 2δ has to hold. Further, since t′′ − 1 ≥ tmin (vk−1 ) = tmin (vk ) − δ, we get that t ≥ t′′ + 2δ > tmin (vk ) + δ. Next, note that there can be no failed workers in Mi′ , as Mi′ ⊆ succGW (w′′ ). Additionally, since t′′ ≤ t − 2δ, all workers in Mi′ were assigned before time t. Hence, there can be no successful worker in Mi′ , as otherwise w′′ would not be the last successful worker assigned to v ′′ before time t. We get that Mi′ contains only malicious workers. Next, let wj = (v ′ , t′ ) with j ̸= i be a different failed worker in W (if there is more than one). If v ′ ̸= v, we immediately get Mi′ ∩ Mj′ = ∅ because Mi′ and Mj′ belong to different tasks. Thus, consider the case that v ′ = v. If t′ ≤ t′′ , we get Mi′ ∩Mj′ = ∅ because all workers in Mj′ were assigned before time t′ . Otherwise, if t′ > t′′ , assume for contradiction that Mi′ ∩ Mj′ ̸= ∅. Since both Mi′ and Mj′ consist of only malicious workers and directly follow the last successful worker assigned to task v ′′ before time t and t′ , respectively, we have Mi′ = Mj′ and w′′ is this last successful worker for both wi and wj . But then, w′′ is linked at either time t or time t′ , which contradicts that w′′ is not linked by Theorem 13. We conclude that Mi′ ∩ Mj′ = ∅ has to hold. Finally, consider some Mj with 1 ≤ j ≤ ℓ + 1. If j = i, we immediately get Mi′ ∩ Mj = ∅ as Mi and Mi′ belong to different tasks. If j > i, note that no worker in Mj was assigned before time t by Theorem 11. As all workers in Mi′ were assigned before time t, we get Mi′ ∩ Mj = ∅. Lastly, if j < i, assume for contradiction that Mi′ ∩ Mj ̸= ∅. Since Mi′ contains only malicious workers and Mj is followed by an honest worker wj = (v ′ , t′ ), we get that t′ > t′′ has to hold. To connect wj with wi in the sequence, there needs to be a successful worker assigned to task v ′ that was assigned between times t′′ and t, because our construction only moves downwards when a successful worker is encountered and the assignment times of the honest workers are non-decreasing by Theorem 11. But then, w′′ would not be last successful worker assigned to task v ′ before time t, which is a contradiction. We conclude that Mi′ ∩ Mj = ∅ has to hold.
19
3.5
Correctness and Work Bound
It remains to show that it is unlikely for a random assignment A of workers to tasks to contain a witness sequence that is valid w.r.t. A. We start by counting the number of malicious assignments A has to perform for a witness sequence W to be valid w.r.t. A. Intuitively, each downwards movement from a task v to a task v ′ ∈ succG (v) increases the number of malicious workers in W by at least δ − 1, as the assignments to v ′ are delayed by δ rounds relative to v. By the same argument, the number of malicious workers decreases by δ for each upwards movement. However, as each upwards movement is associated with a set M ′ consisting of 2δ additional malicious workers, we still get an overall increase of δ malicious workers. We provide a formal bound with the following two lemmas. Lemma 19 (Additional Malicious Workers). For a task graph G = (V, E) and its worker graph GW = (VW , EW ), let A be an assignment of workers to tasks and let W = ((M1 , M1′ , w1 ), . . . , ′ , w )) be a witness sequence that is valid w.r.t. A. If w = (v, t) failed (Mℓ , Mℓ′ , wℓ ), (Mℓ+1 , Mℓ+1 i ⊥ for 1 ≤ i ≤ ℓ, we have |Mi′ | ≥ min{2δ, tmax (v) − t + δ + 1}. Proof of Theorem 19. Since wi failed, we have t ≥ tmin (v) + δ and Mi′ = {(v ′ , t′′ ), . . . , (v ′ , min{t′′ + 2δ − 1, tmax (v ′ )})} for a v ′ ∈ predG (v) and t′′ ≤ t − 2δ (cf. Theorem 4, Property (2)). If t′′ + 2δ − 1 ≤ tmax (v ′ ), we have |Mi′ | = (t′′ + 2δ − 1) − t′′ + 1 = 2δ. Otherwise, if t′′ + 2δ − 1 > tmax (v ′ ), we have |Mi′ | = tmax (v ′ ) − t′′ + 1. As we also have tmax (v ′ ) = tmax (v) − δ and t′′ ≤ t − 2δ, we obtain |Mi′ | = tmax (v ′ ) − t′′ + 1 ≥ tmax (v) − δ − (t − 2δ) + 1 = tmax (v) − t + δ + 1.
Lemma 20 (Total Number of Malicious Workers). For a task graph G = (V, E) and its worker graph GW = (VW , EW ), we consider an assignment A of workers to tasks. Further, Let W = ((M1 , M1′ , w1 ), . . . , (Mℓ , Mℓ′ , wℓ ), (Mℓ+1 , ∅, ⊥)) be a witness sequence that is valid w.r.t. A. Then, there are at least m ≥ max{(δ − 1) · ℓ, γ} malicious workers in MW ∪ M′W . Proof. We prove the statement by induction over ℓ. For ℓ = 0, we have W = ((M1 , ∅, ⊥)) and M1 = {(v, tmin (v)), . . . , (v, tmax (v))} for some task v ∈ V . Hence, there are at least γ malicious workers in M1 = MW and the lemma holds. Now, for an arbitrary, but fixed ℓ, we have that for each valid witness sequence W containing ℓ honest workers there are at least max{(δ − 1) · ℓ, γ} malicious workers in MW ∪ M′W . We extend our claim to the case where W = ′ ,w ((M1 , M1′ , w1 ), . . . , (Mℓ+1 , Mℓ+1 ℓ+1 ), (Mℓ+2 , ∅, ⊥)) contains exactly ℓ + 1 honest workers. To this end, let wℓ+1 := (v, t) and consider the valid witness sequence W = ((M1 , M1′ , w1 ), . . . , (Mℓ , Mℓ′ , wℓ ), (Mℓ+1 ∪ M , ∅, ⊥)), where M = {(v, t), . . . , (v, tmax (v))} extends Mℓ+1 with malicious workers as far as possible to the right. By the induction hypothesis, we have that MW ∪ M′W contains at least max{(δ − 1) · ℓ, γ} malicious workers. We now consider two cases. If wℓ+1 = (v, t) was successful, we have Mℓ+2 = {(v ′ , t + 1), . . . , (v ′ , tmax (v ′ ))} for some v ′ ∈ succG (v). From tmax (v ′ ) = tmax (v) + δ, it follows that |Mℓ+2 | = tmax (v ′ ) − (t + 1) + 1 = tmax (v) − t + δ = |M | + δ − 1. ′ and as all involved sets are disjoint, we have Due to MW = (MW ∪ Mℓ+2 ) \ M and M′W = MW ′ ′ ′ | + δ − 1. As |MW ∪ MW | = |MW ∪ MW | + |Mℓ+2 | − |M |. Hence, |MW ∪ M′W | = |MW ∪ MW ′ contains at least max{(δ − 1) · ℓ, γ} malicious workers, we conclude that M ′ MW ∪ MW W ∪ MW contains at least max{(δ − 1) · (ℓ + 1), γ} malicious workers.
20
′ | ≥ min{2δ, t If wℓ+1 = (v, t) failed, we know that |Mℓ+1 max (v) − t + δ + 1} by Theorem 19. We distinguish between two subcases. If t > tmax (v) − δ, then Mℓ+2 = ∅ and min{2δ, tmax (v) − ′ | ≥ t t + δ + 1} = tmax (v) − t + δ + 1. Thus, we have |Mℓ+1 max (v) − t + δ + 1 = |M | + δ. ′ Otherwise, if t ≤ tmax (v) − δ, we have Mℓ+2 = {(v , t), . . . , (v ′ , tmax (v ′ ))} for some v ′ ∈ predG (v) ′ | ≥ 2δ. From t ′ and min{2δ, tmax (v) − t + δ + 1} = 2δ. Thus, we have |Mℓ+1 max (v ) = tmax (v) − δ, it follows that ′ |Mℓ+2 | + |Mℓ+1 | ≥ tmax (v ′ ) − t + 1 + 2δ = tmax (v) − t + 1 + δ = |M | + δ. ′ Due to MW = (MW ∪ Mℓ+2 ) \ M and M′W = M′W ∪ Mℓ+1 and as all involved sets are disjoint, we ′ ′ ′ have |MW ∪MW | = |MW ∪MW |+|Mℓ+2 |+|Mℓ+1 |−|M |. Hence, in both subcases, |MW ∪M′W | ≥ |MW ∪M′W |+δ. As MW ∪M′W contains at least max{(δ −1)·ℓ, γ} malicious workers, we conclude that MW ∪ M′W contains at least max{(δ − 1) · (ℓ + 1), γ} malicious workers.
Lemma 20 gives us a lower bound on the number of malicious assignments that need to happen for a fixed witness sequence to be valid. This immediately yields the following upper bound for the probability of a fixed witness sequence being valid w.r.t. a random assignment of workers to tasks. Corollary 21 (Probability of a Valid Witness Sequence). For a task graph G = (V, E) and its worker graph GW = (VW , EW ), let W = ((M1 , M1′ , w1 ), . . . , (Mℓ , Mℓ′ , wℓ ), (Mℓ+1 , ∅, ⊥)) be a fixed witness sequence in GW . Further, let A be a random assignment of workers to tasks, where each worker is independently malicious with probability β and honest with probability (1 − β). The probability that W is valid w.r.t A is at most β m where m = |M| + |M′ | ≥ max{(δ − 1) · |H|, γ}. Next, we count the total number of witness sequences with fixed sizes |M|, |H| and |F |. Lemma 22 (Number of Witness Sequences). For a task graph G = (V, E) and its worker graph GW = (VW , EW ), the number of witness sequences with fixed sizes |M|, |H| and |F| in GW is at · (2γd)|H| , where d ≥ max{indeg(G), outdeg(G)}. most n · |M|+|H| |H| Proof. There are n possible tasks at which a witness sequence can start. Further, for each of the |H| many honest workers in a witness sequence, there are at most d many options to which task the sequence moves next. Therefore, there are at most n · d|H| many sequences of tasks a witness sequence can traverse. Given such a sequence of tasks, we count the number of witness sequences that follow this sequence of tasks. To this end, we encode each triple (M, M ′ , w) of a witness sequence in the following way. First, we represent (M, w) as a string on {0, 1, 2}∗ that starts with a number of 0-entries equal to |M | followed by a 1 if w is a successful worker, a 2, if w is a failed worker, or no additional symbol, if w =⊥. Next, we encode M ′ simply by the time t when the first worker in M ′ was assigned, which implicitly also fixes the size of M ′ . Concatenating the resulting strings of all triples yields a unique representation of the witness sequence. We now count the number of {0, 1, 2}-strings with exactly |M| 0-entries and exactly |H| 1-or 2-entries, of which exactly |F | are a 2-entries. There are |M|+|H| ways to place the 1-or-2-entries |H| in the string and |H| ways to choose which of them are a 2-entry. Further, there are at most γ |F | options for when the first worker of a set M ′ can be assigned, yielding another factor of γ |F | . In total, we obtain that the number of witness sequences with fixed sizes |M|, |H|, and |F | is at most |M| + |H| |H| |M| + |H| |H| |F | n·d · · ·γ ≤n· · (2γd)|H| . |H| |F| |H|
21
Finally, we show that it is unlikely for a valid witness sequence to exist by combining Theorem 21 and Theorem 22. This proves that, w.h.p., the computation will succeed. Lemma 23 (Correctness). Let G be a task graph with indegree and outdegree bounded by d. If δ ≥ max{2, 4/(α2 ln2 1/β), (2 log1/β (2eγd))/α + 1} and γ ≥ ((c+5) log1/β 2)/(1−α) log n for any parameter 0 < α < 1, the algorithm terminates correctly on G, w.h.p. Proof. Let A be a random assignment of workers to tasks, where each worker is independently malicious with probability β and honest with probability (1−β). We show that no witness sequence in GW is valid w.r.t A, w.h.p. From the contraposition of Theorem 6, it follows that A does not cause the computation to fail, w.h.p., which proves the lemma. Before we start, we establish a helpful bound for an arbitrary parameter 0 < α < 1: α≥
log1/β (2eδγd) δ−1
(⋆)
To reduce the dependency on γ and d, we do this in two steps, i.e., we separately prove α/2 ≥ log1/β (δ) log1/β (2eγd) and α/2 ≥ δ−1 for different bounds on δ. δ−1
We can directly solve the first inequality
for δ:
log1/β (2eγd) 2 log1/β (2eγd) ⇐⇒ δ ≥ +1 δ−1 α √ For the second inequality, we use δ ≥ max{2, 4/(α2 ln2 1/β)} and x > ln x for x > 0 to obtain: √ √ √ √ δ≥2 2 2 δ δ δ ln(δ) 4 2 =⇒ δ ≥ =⇒ α ln 1/β ≥ √ = = ≥ ≥ δ≥ 2 2 α ln 1/β δ δ − δ/2 δ−1 δ−1 α ln 1/β δ α/2 ≥
Combining the inequalities yields (⋆) for δ ≥ max{2, 4/(α2 ln2 1/β), (2 log1/β (2eγd))/α + 1}. Additionally, Theorem 20 yields |H| ≤ m/(δ−1) and m ≥ γ. We employ the union bound to combine the results of Theorem 21 and Theorem 22 obtaining for the probability that any witness sequence W|M|,|H|,|F | with fixed sizes|M|, |H| and |F | that is valid w.r.t. A exists. |M| + |H| Pr[∃W|M|,|H|,|F | valid w.r.t. A] ≤ n · · (2γd)|H| · β m |H| m + m/(δ−1) m ≤n· · (2γd) /(δ−1) · β m (|M| ≤ m, |H| ≤ m/(δ−1)) m/(δ−1) m e(m + m/(δ−1)) /(δ−1) m ≤n· · (2γd) /(δ−1) · β m m/(δ−1) = n · (eδ) /(δ−1) · (2γd) /(δ−1) · β m m
m
= n · (2eδγd) /(δ−1) · β m m
= n · (1/β )( /(δ−1))·log1/β (2eδγd) · (1/β )−m m
= n · (1/β )−m+m·(
log1 (2eδγd)/(δ−1)) /β
≤ n · (1/β )−m(1−α)
(⋆)
≤ n · (1/β )−γ(1−α)
(m ≥ γ)
≤ n · (1/β )
−(c+5)(log1/β 2) log n
= n · n−c−5 ≤ n−c−4 22
(γ ≥ (c+5) log1/β 2/(1−α) log n)
We apply the union bound three more times to extend the high probability result to all possible values of |M|, |H|, and |F |. As none of these sets can contain more than γn workers, we obtain the probability for any valid witness sequence W existing: XXX Pr[∃W|M|,|H|,|F | valid w.r.t A] ≤ (γn)3 · n−c−4 ≤ n−c Pr[∃W valid w.r.t. A] ≤ |M| |H| |F |
using γ 3 ≤ n for a sufficiently large n as γ = O(log n). Lastly, we prove that only very few honest workers have to execute the task they are assigned to in expectation. Therefore, the expected total work performed by honest workers is very small. Lemma 24 (Work Bound). Let G = (V, E) be a task graph. For a correct execution of the algorithm and for each task v ∈ V , if δ ≥ ((c+1) log1/β log n)/2 and γ = O(log n), then the total work performed by honest workers assigned to v is 1 + o(1) in expectation. The total work performed by all honest workers is n(1 + o(1)) in expectation. Proof. As we consider a succeeding execution of the algorithm, we have at least one computation at each task v ∈ V . As a worst case assumption let the first computation occur at (v, tmin (v)), allowing more opportunities for other workers to have to perform a recomputation. Let Xi be the binary random variable with Xi = 1 iff we have a recomputation at (v, i) for tmin (v) < i ≤ tmax (v). A recomputation at (v, i) implies that (v, i) did not receive the output of v from its predecessors from task v. As every honest worker would forward the output, this further implies the existence of a contiguous sequence of 2δ malicious workers blocking the forwarding. Thus, we have Pr[Xi = 1] ≤ β 2δ and E[Xi ] ≤ β 2δ . As another worst case assumption, let a computation at every worker be possible independent on whether its predecessors already performed a computation. We obtain using 2δ ≥ (c + 1) log1/β log n: E[#computations at v] ≤ 1 +
γ X
E[Xi ]
i=2
≤1+
γ X
β 2δ
i=1
= 1 + γ · β 2δ ≤ 1 + γ · β (c+1) log1/β log n = 1 + γ · log−c−1 n = 1 + o(1)
(γ = O(log n))
We extend the result to the total work using the linearity of expectation. We conclude this section by proving our main theorem. Proof of Theorem 8. Fix δ ≥ max{2, 8e/α2 ln2 1/β, (2 log1/β (2eγd))/α + 1, ((c+1) log1/β log n)/2} and fix γ ≥ ((c′ +5) log1/β 2)/(1−α) log n for any parameter 0 < α < 1 (ensuring that δ = O(log1 (d) · log1 log n) /β /β and γ = O(log n)). The correctness follows from Theorem 23. The runtime follows from the fact that the supervisor assigns the final worker to any task of depth D in round (D − 1) · δ + γ = O(D log1/β (d) · log1/β log n + log n). By construction, each honest worker performs at most one computation for each time it was assigned. The verification and communication bounds follow from the fact that each worker interacts with O(dδ) = O(d log1/β (d) · log1/β log n) other workers. 23
The bound for task executions and total work was proven in Theorem 24. For each initial task, the source needs to send the input to the γ workers assigned to it and for each final task, the target needs to receive the output from each of the γ workers assigned to it and verify each of them at most once. Finally, the supervisor assigns γ = O(log n) workers to each of the n tasks, introduces each worker up to dδ = O(d log1/β (d) · log1/β log n) times, and introduces the source O(log n) times for each initial task. This yields O(n log n) assignments and O(nd log n · log1/β (d) · log1/β log n) introductions.
4
Conclusion
Our work is motivated by large-scale volunteer-driven distributed computing that is open to a wide range of workers. We assume the existence of a lightweight but reliable supervisor that orchestrates the solution process using unreliable workers. The role of the supervisor is very minimal and is limited to scheduling workers to tasks, and not to perform any computations. The problem to be solved is represented as a task graph that is a DAG G, whose nodes are individual tasks and whose edges model precedence relationships. The inputs are fed into the initial tasks (with indegree zero) and collected from the final tasks (with outdegree zero). Each worker is malicious with constant probability β ∈ [0, 1) or honest with probability (1 − β). In the setting where β > 1/2, traditional approaches that assign a quorum of logarithmically many workers to each task and then use the majority outcome from the quorum will not work. We show for the first time how a setting with a majority of malicious workers can be handled. Instead of performing a majority vote, we assign logarithmically many workers to each task one by one. By having the workers provide their output to their 2δ successors, we reduce the work overhead for the honest workers. Similarly, each worker is only responsible to provide the output to 2δ workers of each successor task. We pipeline the assignment of workers to tasks of different levels to ensure that the computation terminates quickly. Our work raises several important questions that warrant further study. Our focus is on problems where the claimed output for an individual task can be verified easily. Sorting and matrix multiplication can be decomposed into such verifiable tasks [3]. However, we believe that many more problems could potentially be decomposed in a similar fashion and benefit from the supervised distributed computing framework. Additionally, it would be interesting to explore whether cryptographic verification mechanisms, such as SNARKs and SNARGs, or hardware based verification mechanisms [18] can be leveraged within our framework. Since our supervisor is very lightweight, we believe that an automated but reliable process (such as a smart contract) could emulate its role, though this requires careful investigation. Finally, studying heterogeneous DAGs, where some tasks are easily verifiable while others require more care, presents a promising direction.
References [1] Eyad Alkassar, Sascha Böhme, Kurt Mehlhorn, and Christine Rizkallah. A framework for the verification of certifying computations. J. Autom. Reason., 52(3):241–273, 2014. [2] Antonio Fernández Anta, Chryssis Georgiou, Miguel A. Mosteiro, and Daniel Pareja. Multiround master-worker computing: A repeated game approach. In 35th IEEE Symposium on Reliable Distributed Systems (SRDS 2016), pages 31–40, 2016. [3] John Augustine, Christian Scheideler, and Julian Werthmann. Supervised distributed computing. In European Conference on Parallel Processing, pages 48–62. Springer, 2025. 24
[4] Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, and Moni Naor. Checking the correctness of memories. In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 90–99. IEEE Computer Society, 1991. [5] Alessandro Chiesa. Succinct non-Interactive arguments. PhD thesis, Massachusetts Institute of Technology, 2014. [6] Evgenia Christoforou, Antonio Fernández Anta, Chryssis Georgiou, and Miguel A. Mosteiro. Algorithmic mechanisms for reliable master-worker internet-based computing. IEEE Trans. Computers, 63(1):179–195, 2014. [7] Evgenia Christoforou, Antonio Fernández Anta, Chryssis Georgiou, and Miguel A. Mosteiro. Internet computing: Using reputation to select workers from a pool. In 4th International Conference on Networked Systems (NETYS 2016), pages 137–153, 2016. [8] Evgenia Christoforou, Antonio Fernández Anta, Kishori M. Konwar, and Nicolas C. Nicolaou. Evaluating reliability techniques in the master-worker paradigm. In 15th IEEE International Symposium on Network Computing and Applications (NCA 2016), pages 183–190, 2016. [9] Giovanni Di Crescenzo, Matluba Khodjaeva, Delaram Kahrobaei, and Vladimir Shpilrain. A survey on delegated computation. In Volker Diekert and Mikhail V. Volkov, editors, Developments in Language Theory - 26th International Conference, DLT 2022, Tampa, FL, USA, May 9-13, 2022, Proceedings, volume 13257 of Lecture Notes in Computer Science, pages 33–53. Springer, 2022. [10] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. In 6th Symposium on Operating System Design and Implementation (OSDI 2004), pages 137– 150. USENIX Association, 2004. [11] Joan Feigenbaum. Overview of interactive proof systems and zero-knowledge. Contemporary Cryptology: The Science of Information Integrity, pages 423–439, 1992. [12] Antonio Fernández, Chryssis Georgiou, Luis López, and Agustı́n Santos. Reliably executing tasks in the presence of malicious processors. In 19th International Conference on Distributed Computing (DISC 2005), pages 490–492, 2005. [13] Antonio Fernández, Luis López, Agustı́n Santos, and Chryssis Georgiou. Reliably executing tasks in the presence of untrusted entities. In 25th IEEE Symposium on Reliable Distributed Systems (SRDS 2006), pages 39–50, 2006. [14] Michael T. Goodrich. Pipelined algorithms to detect cheating in long-term grid computations. Theor. Comput. Sci., 408(2-3):199–207, 2008. [15] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13–30, 1963. [16] Kishori M. Konwar, Sanguthevar Rajasekaran, and Alexander A. Shvartsman. Robust network supercomputing with unreliable workers. J. Parallel Distributed Comput., 75:81–92, 2015. [17] E. Korpela, D. Werthimer, D. P Anderson, J. Cobb, and M. Lebofsky. SETI@home — massively distributed computing for SETI. Computing in Science & Engineering, 3(1):78–83, 2001.
25
[18] Mengyuan Li, Yuheng Yang, Guoxing Chen, Mengjia Yan, and Yinqian Zhang. Sok: Understanding design choices and pitfalls of trusted execution environments. In Proceedings of the 19th ACM Asia Conference on Computer and Communications Security, ASIA CCS ’24, page 1600–1616, New York, NY, USA, 2024. Association for Computing Machinery. [19] Ross M. McConnell, Kurt Mehlhorn, Stefan Näher, and Pascal Schweitzer. Certifying algorithms. Comput. Sci. Rev., 5(2):119–161, 2011. [20] Anca Nitulescu. zk-snarks: A gentle introduction. Ecole Normale Superieure, 2020. [21] Thomas Schickinger and Angelika Steger. Diskrete Strukturen 2. Springer-Lehrbuch. Springer, Berlin, Germany, 1st edition, 2002. Korrigierter Nachdruck. [22] Jason D. Sonnek, Mukesh Nathan, Abhishek Chandra, and Jon B. Weissman. Reputationbased scheduling on unreliable distributed infrastructures. In 26th IEEE International Conference on Distributed Computing Systems (ICDCS 2006), page 30. IEEE Computer Society, 2006. [23] Roberto Tamassia. Authenticated data structures. In Proc. of 11th European Symposium on Algorithms (ESA 2003), pages 2–5, 2003.
26
A
Pseudocode
Algorithm 1: Assigning many workers (Supervisor) 1 foreach v ∈ V 2 3
do tmin (v) ← (D(v) − 1) · δ + 1 tmax (v) ← (D(v) − 1) · δ + γ
// first round of assignments to v // last round of assignments to v
4 for round t ← 1 to γ + (D − 1) · δ do 5 6 7
8 9 10 11 12 13
ψ(t) := {v ∈ V | t ∈ [tmin (v), tmax (v)]} foreach v ∈ ψ(t) do Assign worker w to (v, t) independently, with probability β to be malicious and probability 1 − β to be honest Instruct workers assigned to (v, t − 2δ), . . . , (v, t − 1) to send output of v to w if w fails to verify all these outputs then if v is an initial task then Instruct the source to send the input of v to w else Instruct workers assigned to (v ′ , t − 2δ), . . . , (v ′ , t − 1) with v ′ ∈ predG (v) to send input of v to w
Algorithm 2: Assigning many workers (Worker assigned to task v) 1 upon receiving output candidates of v 2 3 4 5 6 7 8 9
foreach output candidate o do if Verification of o succeeds then success ← true break if success = true then Remain in system for 2δ rounds to provide output to later workers else Notify supervisor of failure to verify outputs
10 upon receiving input candidates of v from workers assigned to v ′ ∈ predG (v) 11 12 13 14 15 16 17 18 19
foreach input candidate i do if Verification of i succeeds then success[v ′ ] ← true break if success[v ′ ] = true for each v ′ ∈ predG (v) then Compute output Remain in system for 2δ rounds to provide output to later workers else Remain in system for 2δ rounds to provide error to later workers
27
Algorithm 3: Supervised Path Computation (Supervisor’s Logic) Input: Number of tasks n, Source, Target and a black-box to assign the workers /* Supervisor State Initialization
*/
1 P ← array of size n, initialized to NULL
// Stores assigned workers // Current task index
2 i←1 3 Procedure SupervisedPathComputation() 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
AssignNewWorker(1) // Start with the first task while i ≤ n do worker id ← P [i] message ← WaitForMessage(worker id) if message is TIMEOUT then AssignNewWorker(i) // Worker failed, re-assign same task else if message is DONE then if i < n then i←i+1 // Proceed to next task AssignNewWorker(i) else IntroduceWorkerToTarget(P [n], Target) target message ← WaitForMessage(Target) if target message is DONE then i←i+1 // Success! Terminate loop else AssignNewWorker(n) // Target rejected n-th worker else if message is REJECT then if i > 1 then i←i−1
// Rollback to previous task // Re-assign worker for rolled-back task
AssignNewWorker(i)
25 Function AssignNewWorker(i): 26 27 28 29 30 31 32
new worker ← SampleWorker() P [i] ← new worker if i = 1 then IntroduceWorkerToSource(new worker, Source) else previous worker ← P [i − 1] IntroduceWorkers(previous worker, new worker)
28
B
Improved Bound and Infeasibility Results
In this section, we provide some additional analysis for the algorithms presented in [3]. In Section B.1, we improve the allowed fraction of malicious workers for the runtime proof of the path algorithm from β ≤ 1/12 to β < 1/2. In Section B.2, we prove that this new bound for β is tight. More specifically, for any β > 1/2, the path algorithm requires exponential time to terminate, w.h.p. Finally, we prove a similar result for the DAG algorithm in Section B.3. The authors of [3] provide a bound β ≤ (1/(2(2d+1)))2+ε for the DAG algorithm to terminate within O((D+log n)/ε), w.h.p. We almost match this bound by proving that the DAG algorithm requires exponential time to terminate for β > ln c/c2 for c = (d+1)/2.
B.1
Improved Bound for Path Graphs
We start by presenting a new analysis of the path algorithm from [3]. Specifically, we improve the bound on the number of malicious workers under which the algorithm still terminates correctly in linear time from β ≤ 1/12 to β < 1/2. In the path algorithm, the supervisor assigns workers to tasks sequentially and processes their responses. A worker assigned to vi must reply with either DONE (execution completed) or REJECT (input invalid or missing). If a worker replies DONE, the supervisor proceeds to vi+1 (or to the target if i = n). If the reply is REJECT, the supervisor removes the workers assigned to vi−1 and vi from the system and reassigns a new worker to vi−1 . In case the supervisor does not receive DONE/REJECT within some specified time, it reassigns a new worker to vi . The computation terminates once the target replies with DONE. The pseudocode of the path algorithm is provided as Algorithm 3. Theorem 25. For a path graph of size n it holds that: If β < 1/2, the supervised computation √ terminates correctly under any adversarial strategy in n/(1−2β) + Θ ( n log n/(1−2β)) rounds, w.h.p. Furthermore, the source just needs to send the input 1/(1−2β) times, and the target just needs to receive the solution 1/(1−2β) times, in expectation. Proof. According to [3], always sending REJECT is a dominant adversarial strategy. Thus, we prove the statement for that strategy and immediately obtain the general result. When the always-REJECT strategy is used, each adversary is immediately rolled back after assignment. Thus, whenever the supervisor makes an assignment to a task vi for 1 < i ≤ n, the worker assigned to vi−1 is guaranteed to be honest. Let Xt be a binary random variable representing the progress we make in round t. If the supervisor assigns an honest worker, the computation proceeds to the next task and we have Xt = +1. The supervisor assigning a malicious worker results in a rollback and we have Xt = −1. P Further, let ST = Tt=1 Xt be the net progress we make in T rounds. The supervised computation terminates if it reaches the target, i.e., if the net progress XT reaches n + 1. Our goal is to prove that the computation terminates after T = n/1−2β + ∆ rounds, w.h.p., where we will choose ∆ > 0 later to control the failure probability. We start by computing the expected progress we make in each round: E[Xt ] = (+1) · Pr[Xt = +1] + (−1) · Pr[Xt = −1] = (1 − β) − β = 1 − 2β P By linearity of expectation, we have E[ST ] = Tt=1 E[Xt ] = T (1 − 2β). We will employ a variant on Hoeffding’s inequality [15] that states for the sum ST of independent
29
random variables X1 , . . . , XT with ai ≤ Xi ≤ bi for 1 ≤ i ≤ T : Pr[ST − E[ST ] ≤ x] ≤ exp − PT
!
2x2
i=1 (bi − ai )
2
In our case, we have ai = −1 and bi = +1 for 1 ≤ i ≤ T , which allows us to simplify the bound: 2x2 x2 Pr[ST − E[ST ] ≤ x] ≤ exp − = exp − 4T 2T Our goal is to bound the failure probability. We transform the failure event to match the bound: ST < n + 1 ⇐⇒ ST ≤ n ⇐⇒ ST − E[ST ] ≤ n − E[ST ] n + ∆ (1 − 2β) ⇐⇒ ST − E[ST ] ≤ n − 1 − 2β ⇐⇒ ST − E[ST ] ≤ −∆(1 − 2β) In preparation of our application of Hoeffding’s Inequality, we solve the following inequality for ∆ using the quadratic formula. (∆(1 − 2β))2 ≥ c ln n n + ∆) 2( 1−2β
n +∆ 1 − 2β 2cn ln n ⇐⇒ (1 − 2β)2 · ∆2 − 2c ln n · ∆ − ≥0 1 − 2β q ln n 2c ln n ± (2c ln n)2 + 4(1 − 2β)2 2cn 1−2β ⇐⇒ ∆ ≥ 2(1 − 2β)2 q ln n c ln n ± (c ln n)2 + (1 − 2β)2 2cn 1−2β ⇐⇒ ∆ ≥ (1 − 2β)2 ⇐⇒ (∆(1 − 2β))2 ≥ 2c ln n ·
Note that we are only interested in the positive root. As we want to pick ∆ as small as possible, √ we have ∆ = Θ ( n log n/(1−2β)). We are now ready to apply Hoeffdings inequality choosing ∆ as above: ! (∆(1 − 2β))2 Pr[ST < n + 1] ≤ exp − ≤ exp(−c ln n) ≤ n−c n 2( 1−2β + ∆) It remains to prove the expected number of send and receives for the source and the target. Recall that E[Xt ] = 1−2β is the expected progress a worker make in round t for a task. Therefore, it requires 1/(1−2β) rounds to progress a task in expectation. We conclude that the source needs to send the input 1/(1−2β) times and the target needs to receive the output 1/(1−2β) times, in expectation.
30
B.2
Infeasibility Result for Path Graphs
In this section, we prove that the bound from Theorem 25 is tight. More specifically, we prove that for any β > 1/2, the path algorithm requires exponential time to terminate, w.h.p. To achieve this, we fix an adversarial strategy and describe the resulting computation with a Markov chain that has two absorbing states representing the source and the target. Using the well-established gambler’s ruin problem (see, e.g. [21]), we prove that once the computation reaches the first task, it is exponentially more likely to return to the source than to reach the target. Finally, we conclude that an exponential number of such trials is required until the target is reached for the first time, w.h.p. Theorem 26. For a path graph of size n it holds that: If β > 1/2, there is an adversarial strategy s.t. the supervised computation requires exponential time to terminate correctly, w.h.p. Proof. We consider the adversarial strategy of always sending a REJECT. We recall from the proof of Theorem 25 that we can model the progress we make in each round t under this adversarial strategy with a random variable Xt s.t. Xt = +1, if the supervisor assigns an honest worker in round t, and Xt = −1, if the supervisor assigns a malicious worker in round t. Notably, these variables are independent and identically distributed. We describe the computation with a Markov chain with states 0, . . . , n + 1 that describe the net progress. State 0 represents the computation being located at the source, state i represents the computation being located at task i for 1 ≤ i ≤ n, and state n + 1 represents the computation having reached the target. As discussed above, the chain has transition probabilities p := Pr[i → i + 1] = 1 − β and q := Pr[i → i − 1] = β for 1 ≤ i ≤ n. Our first goal is to bound the probability f1,n+1 that the chain reaches state n + 1 before reaching state 0 after reaching 1 for the first time. Thus we choose the initial state to be 1 (which is reasonable, as the supervisor will eventually assign an honest worker to the first task, w.h.p.), and we define the states 0 and n + 1 to be absorbing, i.e., Pr[0 → 0] = 1 and Pr[1 → 1] = 1. This is an instance of the classic gambler’s ruin problem for which there are numerous sources, e.g., [21]. We obtain the following identity for f1,n+1 from the literature: f1,n+1 =
1 − q/p 1 − (q/p)n+1
We have q/p = β/(1−β), which increases monotonously on [0,1). β > 1/2 yields q/p > 1. For such fractions, we have for any n ≥ 1: (q/p)n > 1 ⇐⇒ − (q/p)n < −1 ⇐⇒ (q/p)n+1 − (q/p)n < (q/p)n+1 − 1 ⇐⇒ (q/p)n (q/p − 1) < (q/p)n+1 − 1 q/p − 1 ⇐⇒ < (q/p)−n n+1 q ( /p) −1 We bound f1,n+1 as follows: f1,n+1 =
q/p − 1 1 − q/p = < (q/p)−n n+1 1 − (q/p) (q/p)n+1 − 1
31
We consider an application of the gambler’s ruin problem to be a single trial to reach the target before reaching the source again. It remains to prove that an exponential number of trials is required to reach the target, w.h.p. Let X be a random variable representing the number of independent trials until state n + 1 is reached for the first time. Choosing the exponential threshold T = n−c · (q/p)n , we obtain: Pr[X ≤ T ] = 1 − (1 − f1,n+1 )T ≤ 1 − (1 − (q/p)−n )T ≤ 1 − (1 − T · (q/p)−n )
((1 − x)T ≥ 1 − T x for x ∈ [0, 1])
= T · (q/p)−n = n−c
B.3
Infeasibility Result for DAGs
Finally, we prove that the bound of β ≤ (1/(2(2d+1)))2+ε for the DAG algorithm from [3] is almost tight, too. More specifically, we prove that the DAG algorithm requires exponential time to terminate, w.h.p., if β > ln c/c2 , where c = (d+1)/2 and c ≥ 5. In the DAG algorithm, the supervisor keeps track of a set F ⊆ V of tasks that it considers to be finished. In each round, it assigns workers to all tasks that are not in F , but where all predecessors are in F . A worker assigned to a task v must reply either with DONE (execution completed) or REJECT(R), where R ⊆ V is a subset of predecessors of v from which the worker received an invalid or no input. If a worker replies DONE, the supervisor adds its task to F . If a worker replies REJECT(R), the supervisor removes its task, every task in R and every task reachable from any task in R from F . Additionally, it removes all workers assigned to any of these tasks from the system. If the supervisor receives neither DONE nor REJECT, it removes the worker that failed to reply according to the protocol from the system. If the predecessors of the corresponding task are still in F by the next round, the supervisor will assign a new worker to it. The computation terminates once the target replies with DONE. For our proof, we describe a family of worst-case DAGs, where the DAG algorithm struggles to make progress. Employing several worst-case assumptions, we set up an instance of the gambler’s ruin problem again, and are thus able to argue similarly to Theorem 26. Theorem 27. If β > ln c/c2 where c ≥ 5 and c = (d+1)/2, then there is a DAG G with indeg(G) ≤ d and outdeg(G) ≤ d where the protocol requires exponential time to terminate for some adversarial strategy, w.h.p. Proof. We consider the DAG G = (V, E) with n levels of c2 tasks, i.e., V = {0, . . . , n − 1} × {0, . . . , c2 − 1}. We divide each level into c blocks of c nodes, i.e., block j of level i contains nodes (i, c · j), . . . , (i, c · (j + 1) − 1) for 0 ≤ j ≤ c − 1. For every level i with 0 ≤ i < n − 1, block j of level i is connected to block j of level i + 1 for 0 ≤ j ≤ c − 1 with a complete bipartite graph. Additionally, for 0 ≤ i < n − 1, 0 ≤ j ≤ c − 1, and 0 ≤ k ≤ c − 1, the kth task in block j of level i (i, c · j + k) is connected to the kth task of every block j ′ of level i + 1 (i + 1, c · j ′ + k) with 0 ≤ j ′ ≤ c − 1 and j ′ ̸= j. Figure 6 depicts the connections of two adjacent levels of the DAG for c = 3. It remains to prove that the protocol requires exponential time to terminate on G for some adversarial strategy, w.h.p. Our goal is to set up another instance of the gambler’s ruin problem. To this end, we have all adversaries follow the strategy to always REJECT all their inputs upon assignment. For this strategy, the assignment of a single adversarial worker to block j in level i + 1 32
i
0
1
2
0
1
2
0
1
2
i+1
0
1
2
0
1
2
0
1
2
Block 0
Block 1
Block 2
Figure 6: The connections of two adjacent levels of the DAG for c = 3. The blue edges connect tasks in the same block of levels i and i + 1 with a complete bipartite graph. The red edges connect each task in level i with the corresponding task in each other block in level i + 1.
causes a REJECT to exactly one task in every other block j ′ for j ′ ̸= j of level i and all tasks in block j of level i. This results in the supervisor having to reassign the rejected workers, and all their successors. Specifically, at least all workers in block j of level i and all workers of level i + 1 get reassigned. We model the problem with a Markov chain M with states 0, . . . , n + 1. M is in state i, if i is the last level where any honest workers are assigned. As a worst case assumption, we consider all workers assigned to level i to be honest. Each transition of M corresponds to at least one round of the supervised computation. For M to increase its state (i → i+1), all tasks in level i+1 have to receive an honest assignment as any malicious assignment in level i+1 would result in a reject and thus the removal of all workers in level i + 1. Thus, we obtain using β > ln c/c2 : 2
2
p := Pr[i → i + 1] = (1 − β)c ≤ e−βc < 1/c. For M to decrease its state (i → i − 1), we require a process of at least two rounds. Firstly, at least one task in level i + 1 has to receive a malicious assignment, resulting in a rollback of at least one block in level i. Secondly, at least one task in the block of i that was just rolled back has to receive a malicious assignment, resulting in a rollback of the rest of level i. We obtain using β > ln c/c2 : 2
q := Pr[i → i − 1] ≥ (1 − (1 − β)c )(1 − (1 − β)c ) 2
≥ (1 − e−βc )(1 − e−βc ) > (1 − 1/c)(βc − (βc)2/2)
(1 − e−x ≥ x − x2/2 for x ≥ 0)
> (1 − 1/c) · (ln c/c − ln2 c/2c2 )
(βc < 1)
Note that M has some self loops, where the state neither decreases nor increases. These can be ignored for the gambler’s ruin problem as they do not change the number of steps required to reach any absorbing state. Thus, we are only interested in the ratio q/p. We have q/p >
(1 − 1/c) · (ln c/c − ln2 c/2c2 ) ln c − ln2 c/2c c≥5 = (c − 1) > 1. 1/c c
We conclude that there is a drift towards the source. We can prove that the protocol requires exponential time to terminate, w.h.p., for the always-REJECT strategy analogously to Theorem 26. Note that β > ln((d+1)/2)/((d+1)/2)2 and d = 2c − 1 imply β > ln c/c2 . 33
34