Consider a distributed system with @math processors out of which @math can be Byzantine faulty. In the approximate agreement task, each processor @math receives an input value @math and has to decide on an output value @math such that - the output values are in the convex hull of the non-faulty processors' input values, - the output values are within distance @math of each other. Classically, the values are assumed to be from an @math -dimensional Euclidean space, where @math . In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph @math and the goal is to output vertices that are within distance @math of each other in @math , but still remain in the graph-induced convex hull of the input values. For @math , the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any @math , we show that the task is solvable in asynchronous systems when @math is chordal and @math , where @math is the clique number of @math . In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures.
The was originally introduced in the context of wait-free algorithms in shared memory models @cite_47 @cite_53 . The problem has recently resurfaced in the context of asynchronous message-passing models with crash faults @cite_28 @cite_56 . These papers consider the problem when the validity condition is given as @math , i.e., the output of a processor must satisfy @math and the feasible area is determined also by the inputs of faulty processors. However, it is not difficult to see that under Byzantine faults, this validity condition is not reasonable, as the problem cannot be solved even with one faulty processor.
@cite_28 @cite_47 @cite_56 @cite_53
1967858331 2083306187 2139686511 2042928046
In the classical consensus problem, each of n processors receives a private input value and produces a decision value which is one of the original input values, with the requirement that all processors decide the same value. A central result in distributed computing is that, in several standard models including the asynchronous shared-memory model, this problem has no deterministic solution. The k-set agreement problem is a generalization of the classical consensus proposed by Chaudhuri [ Inform. and Comput., 105 (1993), pp. 132--158], where the agreement condition is weakened so that the decision values produced may be different, as long as the number of distinct values is at most k. For @math it was not known whether this problem is solvable deterministically in the asynchronous shared memory model. In this paper, we resolve this question by showing that for any k < n, there is no deterministic wait-free protocol for n processors that solves the k-set agreement problem. The proof technique is new: it is based on the development of a topological structure on the set of possible processor schedules of a protocol. This topological structure has a natural interpretation in terms of the knowledge of the processors of the state of the system. This structure reveals a close analogy between the impossibility of wait-free k-set agreement and the Brouwer fixed point theorem for the k-dimensional ball. In the classical consensus problem,each of n processors receives a private input value and produces a decision value which is one of the original input values,with the requirement that all processors decide the same value. A central result in distributed computing is that,in several standard models including the asynchronous shared-memory model,this problem has no determinis- tic solution. The k-set agreement problem is a generalization of the classical consensus proposed by Chaudhuri (Inform. and Comput.,105 (1993),pp. 132-158),where the agreement condition is weak- ened so that the decision values produced may be different,as long as the number of distinct values is at most k .F or n>k ≥ 2 it was not known whether this problem is solvable deterministically in the asynchronous shared memory model. In this paper,we resolve this question by showing that for any k<n ,there is no deterministic wait-free protocol for n processors that solves the k-set agreement problem. The proof technique is new: it is based on the development of a topological structure on the set of possible processor schedules of a protocol. This topological structure has a natural interpretation in terms of the knowledge of the processors of the state of the system. This structure reveals a close analogy between the impossibility of wait-free k-set agreement and the Brouwer fixed point theorem for the k-dimensional ball. The condition-based approach identifies sets of input vectors, called conditions, for which it is possible to design an asynchronous protocol solving a distributed problem despite process crashes. This paper establishes a direct correlation between distributed agreement problems and error-correcting codes. In particular, crash failures in distributed agreement problems correspond to erasure failures in error-correcting codes and Byzantine and value domain faults correspond to corruption errors. This correlation is exemplified by concentrating on two well-known agreement problems, namely, consensus and interactive consistency, in the context of the condition-based approach. Specifically, the paper presents the following results: first, it shows that the conditions that allow interactive consistency to be solved despite fc crashes and fc value domain faults correspond exactly to the set of error-correcting codes capable of recovering from fc erasures and fc corruptions. Second, the paper proves that consensus can be solved despite fc crash failures if the condition corresponds to a code whose Hamming distance is fc + 1 and Byzantine consensus can be solved despite fb Byzantine faults if the Hamming distance of the code is 2 fb + 1. Finally, the paper uses the above relations to establish several results in distributed agreement that are derived from known results in error-correcting codes and vice versa. We show that no algorithm exists for deciding whether a finite task for three or more processors is wait-free solvable in the asynchronous read-write shared-memory model. This impossibility result implies that there is no constructive (recursive) characterization of wait-free solvable tasks. It also applies to other shared-memory models of distributed computing, such as the comparison-based model.