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,
In summary, a main contribution of this work is its simplicity. Using gradecast as a building block we present a very simple basic algorithm that solves the consensus problem and two small variations of it that solve multi consensus and approximate agreement. All three algorithms support @math , have the early-stopping property and are asymptotically optimal in their running time (up to a constant multiplicative factor). Aside from the simplicity, following are the properties of the presented algorithms: enumerate The basic algorithm solves the consensus problem and terminates within @math rounds. The first variation solves the approximate agreement problem, with convergence rate of @math , per @math rounds ( within @math rounds it converges to @math ). The message complexity is @math per @math rounds, as opposed to @math of the previous best known results. Moreover, the solution dynamically adapts to the number of failures at each round. The second variation solves @math sequential consensuses within @math rounds, and efficiently overcomes the requirement of synchronized starts of the consensus instances (a requirement assumed by @cite_17 ). enumerate
@cite_17
1972328077
Are randomized consensus algorithms more powerful than deterministic ones? Seemingly so, since randomized algorithms exist that reach consensus in expected constant number of rounds, whereas the deterministic counterparts are constrained by the r ≥ t + 1 lower bound in the number of communication rounds, where t is the maximum number of faults to be tolerated.