Optimal resilience asynchronous approximate agreement
Principles of Distributed Systems: 8th International Conference, OPODIS 2004 …, 2005•Springer
Consider an asynchronous system where each process begins with an arbitrary real value.
Given some fixed ε> 0, an approximate agreement algorithm must have all non-faulty
processes decide on values that are at most ε from each other and are in the range of the
initial values of the non-faulty processes. Previous constructions solved asynchronous
approximate agreement only when there were at least 5 t+ 1 processes, t of which may be
Byzantine. In this paper we close an open problem raised by Dolev et al. in 1983. We …
Given some fixed ε> 0, an approximate agreement algorithm must have all non-faulty
processes decide on values that are at most ε from each other and are in the range of the
initial values of the non-faulty processes. Previous constructions solved asynchronous
approximate agreement only when there were at least 5 t+ 1 processes, t of which may be
Byzantine. In this paper we close an open problem raised by Dolev et al. in 1983. We …
Abstract
Consider an asynchronous system where each process begins with an arbitrary real value. Given some fixed ε> 0, an approximate agreement algorithm must have all non-faulty processes decide on values that are at most ε from each other and are in the range of the initial values of the non-faulty processes.
Previous constructions solved asynchronous approximate agreement only when there were at least 5t+1 processes, t of which may be Byzantine. In this paper we close an open problem raised by Dolev et al. in 1983. We present a deterministic optimal resilience approximate agreement algorithm that can tolerate any t Byzantine faults while requiring only 3t+1 processes.
The algorithm’s rate of convergence and total message complexity are efficiently bounded as a function of the range of the initial values of the non-faulty processes. All previous asynchronous algorithms that are resilient to Byzantine failures may require arbitrarily many messages to be sent.
Springer
