Optimal Resilience Asynchronous Approximate Agreement

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.