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 seminal result of @cite_0 showed that consensus cannot be reached in asynchronous systems in the presence of crash faults. @cite_5 showed that it is however possible to reach in an asynchronous system even with arbitrary faulty behavior when the values reside on the continuous real line. Subsequently, the one-dimensional approximate agreement problem has been extensively studied @cite_5 @cite_10 @cite_36 @cite_41 . Fekete @cite_36 showed that any algorithm reducing the distance of values from @math to @math requires @math asynchronous rounds when @math ; in the discrete setting this yields the bound @math for paths of length @math . Recently, @cite_13 introduced the natural generalisation of approximate agreement and showed that the @math -dimensional problem is solvable in an asynchronous system with Byzantine faults if and only if @math holds for any given @math .
@cite_13 @cite_41 @cite_36 @cite_0 @cite_5 @cite_10
2139686511 1971773339 2010107859 2147056869
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. Consider a network of @math n processes, where each process inputs a @math d-dimensional vector of reals. All processes can communicate directly with others via reliable FIFO channels. We discuss two problems. The multidimensional Byzantine consensus problem, for synchronous systems, requires processes to decide on a single @math d-dimensional vector @math v?Rd, inside the convex hull of @math d-dimensional vectors that were input by the non-faulty processes. Also, the multidimensional Byzantine approximate agreement (MBAA) problem, for asynchronous systems, requires processes to decide on multiple @math d-dimensional vectors in @math Rd, all within a fixed Euclidean distance @math ∈ of each other, and inside the convex hull of @math d-dimensional vectors that were input by the non-faulty processes. We obtain the following results for the problems above, while tolerating up to @math f Byzantine failures in systems with complete communication graphs: (1) In synchronous systems, @math n>max 3f,(d+1)f is necessary and sufficient to solve the multidimensional consensus problem. (2) In asynchronous systems, @math n>(d+2)f is necessary and sufficient to solve the multidimensional approximate agreement problem. Our sufficiency proofs are constructive, giving explicit protocols for the problems. In particular, for the MBAA problem, we give two protocols with strictly different properties and applications. The problem of e-approximate agreement in Byzantine asynchronous systems is well-understood when all values lie on the real line. In this paper, we generalize the problem to consider values that lie in Rm, for m ≥ 1, and present an optimal protocol in regard to fault tolerance. Our scenario is the following. Processes start with values in Rm, for m ≥ 1, and communicate via message-passing. The system is asynchronous: there is no upper bound on processes' relative speeds or on message delay. Some faulty processes can display arbitrarily malicious (i.e. Byzantine) behavior. Non-faulty processes must decide on values that are: (1) in Rm; (2) within distance e of each other; and (3) in the convex hull of the non-faulty processes' inputs. We give an algorithm with a matching lower bound on fault tolerance: we require n > t(m+2), where n is the number of processes, t is the number of Byzantine processes, and input and output values reside in Rm. Non-faulty processes send O(n2 d log(m e max δ(d): 1 ≤ d ≤ m )) messages in total, where δ(d) is the range of non-faulty inputs projected at coordinate d. The Byzantine processes do not affect the algorithm's running time. Much of the past work on asynchronous approximate Byzantine consensus has assumed scalar inputs at the nodes [4, 8]. Recent work has yielded approximate Byzantine consensus algorithms for the case when the input at each node is a d-dimensional vector, and the nodes must reach consensus on a vector in the convex hull of the input vectors at the fault-free nodes [9, 13]. The d-dimensional vectors can be equivalently viewed as points in the d-dimensional Euclidean space. Thus, the algorithms in [9, 13] require the fault-free nodes to decide on a point in the d-dimensional space. In our recent work [12], we proposed a generalization of the consensus problem, namely Byzantine convex consensus (BCC), which allows the decision to be a convex polytope in the d-dimensional space, such that the decided polytope is within the convex hull of the input vectors at the fault-free nodes. We also presented an asynchronous approximate BCC algorithm. In this paper, we propose a new BCC algorithm with optimal fault-tolerance that also agrees on a convex polytope that is as large as possible under adversarial conditions. Our prior work [12] does not guarantee the optimality of the output polytope.