Reaching approximate agreement in the presence of faults

TLDR

The paper studies a variant of the Byzantine Generals problem where processes hold arbitrary real values and aim for approximate agreement, contrasting with Fischer et al.'s result that exact agreement is impossible in asynchronous systems with a single fault. The authors aim to develop algorithms that achieve approximate agreement in both asynchronous and synchronous systems. The algorithms use successive approximation, achieving a provable convergence rate that scales with the ratio of faulty to total processes. They prove lower bounds on convergence rate and demonstrate that their algorithms are optimal.

Abstract

This paper considers a variant of 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 et al, who show that exact agreement with guaranteed termination is not attainable in an asynchronous system with as few as one faulty process. The algorithms work by successive approximation, with a provable convergence rate that depends on the ratio between the number of faulty processes and the total number of processes. Lower bounds on the convergence rate for algorithms of this form are proved, and the algorithms presented are shown to be optimal.