Fast asynchronous Byzantine agreement and leader election with full information
Bruce M. Kapron, David Kempe, Valerie Jean King, Jared Saia, Vishal Sanwalani · ACM Transactions on Algorithms · 2010
We resolve two long-standing open problems in distributed computation by describing polylogarithmic protocols for Byzantine agreement and leader election in the asynchronous full information model with a nonadaptive malicious adversary. All past protocols for asynchronous Byzantine agreement had been exponential, andnoprotocol for asynchronous leader election had been known. Our protocols tolerate up to (1/3 − ϵ) ⋅nfaulty processors, for any positive constant ϵ. They are Monte Carlo, succeeding with probability 1 −o(1) for Byzantine agreement, and constant probability for leader election. A key technical contribution of our article is a new approach for emulating Feige's lightest bin protocol, even with adversarial message scheduling.