Two More Algorithms for Randomized Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3 and O(n^2) Messages and O(1) Round Expected Termination
share
This work describes two randomized, asynchronous, round based, Binary Byzantine faulty tolerant consensus algorithms based on the algorithms of [25] and [26]. Like the algorithms of [25] and [26] they do not use signatures, use O(n^2) messages per round (where each message is composed of a round number and a constant number of bits), tolerate up to one third failures, and have expected termination in constant number of rounds. The first, like [26], uses a weak common coin (i.e. one that can return different values at different processes with a constant probability) to ensure termination. The algorithm consists of 5 to 7 message broadcasts per round. An optimization is described that reduces this to 4 to 5 broadcasts per round for rounds following the first round. Comparatively, [26] consists of 8 to 12 message broadcasts per round. The second algorithm, like [25], uses a perfect common coin (i.e. one that returns the same value at all non-faulty processes) for both termination and correctness. Unlike [25], it does not require a fair scheduler to ensure termination. Furthermore, the algorithm consists of 2 to 3 message broadcasts for the first round and 1 to 2 broadcasts for the following rounds, while [29] consists of 2 to 3 broadcasts per round.
READ FULL TEXT