Reaching Approximate Agreement in the Presence of Faults.

This paper considers a variant on the Byzantine GEnerals problem, in which processes start with arbitrary real values rather than Boolean values or values from some bounded range, and in which approximate, rather than exact, agreement is the desired goal. Algorithms are presented to reach approximate agreement in asynchronous, as well as synchronous systems. The asynchronous agreement algorithm is an interesting contrast to a result of Fischer, Lynch, and Patterson, who show that exact agreement in not attainable in an asynchronous system with a provable convergence rate that depends on the ration between the number of faults and the number of processes. Lower bounds on the convergence rate for algorithms of this form are proven, and the algorithms presented are shown to be optimal. Keywords Agreement protocols fault-tolerance Byzantine Generals Approximate agreement Distributed systems.