Gradecast is a simple three-round algorithm presented by Feldman and Micali. The current work presents a very simple synchronous algorithm that utilized Gradecast to achieve Byzantine agreement. Two small variations of the presented algorithm lead to improved algorithms for solving the Approximate agreement problem and the Multi-consensus problem. An optimal approximate agreement algorithm was presented by Fekete, which supports up to 1 n Byzantine nodes and has message complexity of O(n k ), where n is the number of nodes and k is the number of rounds. Our solution to the approximate agreement problem is optimal,
Approximate Agreement: Approximate agreement was presented in @cite_12 . The synchronous solution provided in @cite_12 supports @math and the convergence rate is @math per round, which asymptotically is @math after @math rounds. To easily compare the different algorithms, we consider the number of rounds it takes to reach convergence of @math . For @cite_12 , within @math rounds the algorithm ensures all non-faulty nodes have converged to @math . The message complexity of @cite_12 is @math per each round of the @math rounds.
@cite_12
2126906505
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 , 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.