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
2151102492 2095126777 2886192190 1997124359
Lattice agreement is a key decision problem in distributed systems. In this problem, processes start with input values from a lattice, and must learn (non-trivial) values that form a chain. Unlike consensus, which is impossible in the presence of even a single process failure, lattice agreement has been shown to be decidable in the presence of failures. In this paper, we consider lattice agreement problems in asynchronous, message passing systems. We present an algorithm for the lattice agreement problem that guarantees liveness as long as a majority of the processes are non-faulty. The algorithm has a time complexity of O(N) message delays, where N is the number of processes. We then introduce the generalized lattice agreement problem, where each process receives a (potentially unbounded) sequence of values from an infinite lattice and must learn a sequence of increasing values such that the union of all learnt sequences is a chain and every proposed value is eventually learnt. We present a wait-free algorithm for solving generalized lattice agreement. The algorithm guarantees that every value received by a correct process is learnt in O(N) message delays. We show that this algorithm can be used to implement a class of replicated state machines where (a) commands can be classified as reads and updates, and (b) all update commands commute. This algorithm can be used to realize serializable and linearizable replicated versions of commonly used data types. The snapshot object is an important tool for constructing wait-free asynchronous algorithms. We relate the snapshot object to the lattice agreement decision problem. It is shown that any algorithm for solving lattice agreement can be transformed into an implementation of a snapshot object. The overhead cost of this transformation is only a linear number of read and write operations on atomic single-writer multi-reader registers. The transformation uses an unbounded amount of shared memory. We present a deterministic algorithm for lattice agreement that used O(log2 n) operations on 2-processor Test & Set registers, plus O(n) operations on atomic single-writer multi-reader registers. The shared objects are used by the algorithm in a dynamic mode, that is, the identity of the processors that access each of the shared objects is determined dynamically during the execution of the algorithm. By a randomized implementation of 2-processors Test & Set registers from atomic registers, this algorithm implies a randomized algorithm for lattice agreement that uses an expected number of O(n) operations on (dynamic) atomic single-writer multi-reader registers. Combined with our transformation this yields implementations of atomic snapshots with the same complexity. This paper studies the lattice agreement problem and the generalized lattice agreement problem in distributed message passing systems. In the lattice agreement problem, given input values from a lattice, processes have to non-trivially decide output values that lie on a chain. We consider the lattice agreement problem in both synchronous and asynchronous systems. For synchronous lattice agreement, we present two algorithms which run in @math and @math rounds, respectively, where @math denotes the height of the input sublattice @math , @math is the number of crash failures the system can tolerate, and @math is the number of processes in the system. These algorithms have significant better round complexity than previously known algorithms. The algorithm by attiya1995atomic takes @math synchronous rounds, and the algorithm by Mavronicolasa mavronicolasabound takes @math rounds. For asynchronous lattice agreement, we propose an algorithm which has time complexity of @math message delays which improves on the previously known time complexity of @math message delays. The generalized lattice agreement problem defined by in faleiro2012generalized is a generalization of the lattice agreement problem where it is applied for the replicated state machine. We propose an algorithm which guarantees liveness when a majority of the processes are correct in asynchronous systems. Our algorithm requires @math units of time in the worst case which is better than @math units of time required by the algorithm of faleiro2012generalized . In a shared-memory system, n independent asynchronous processes, with distinct names in the range 0, ..., N-1 , communicate by reading and writing to shared registers. An algorithm is wait-free if a process completes its execution regardless of the behavior of other processes. This paper considers wait-free algorithms whose complexity adjusts to the level of contention in the system: An algorithm is adaptive (to total contention) if its step complexity depends only on the actual number of active processes, k; this number is unknown in advance and may change in different executions of the algorithm. Adaptive algorithms are presented for two important decision problems, lattice agreement and (6k-1)-renaming; the step complexity of both algorithms is O(k log k). An interesting component of the (6k-1)-renaming algorithm is an O(N) algorithm for (2k-1)-renaming; this improves on the best previously known (2k-1)-renaming algorithm, which has O(Nnk) step complexity. The efficient renaming algorithm can be modified into an O(N) implementation of atomic snapshots using dynamic single-writer multi-reader registers. The best known implementations of atomic snapshots have step complexity O(N log N) using static single-writer multi-reader registers, and O(N) using multi-writer multi-reader registers.