Common Contracts
1 similar Byzantine Agreement contracts
Scalable Byzantine agreement with a random beaconByzantine Agreement • April 23rd, 2012
Abstract. We present two Monte Carlo algorithms for efficiently computing Byzan- tine agreement in the partially synchronous communication model. The algorithms assume the existence of a random beacon, which is a stream of random bits known to all processors. Both algorithms terminate in O(1) expected time. The first algo- rithm sends O(B + n log n) messages in total, where B is the maximum number of messages sent by the bad processors in any round and n is the number of pro- cessors. It ensures all processors reach agreement. The second algorithm sends O˜(1) messages per processor, and is thus load-balanced, and ensures all but a o(1) fraction of the processors reach agreement. Both algorithms succeed with prob- ability 1 O(1/nk), even against an adaptive adversary that takes over up to a 1/3 g fraction of the processors, for any fixed positive values g and k. We prove the correctness of both algorithms and provide empirical evidence that they re- quire significantly less bandwidth th
