Byzantine Agreement in Expected Polynomial Time

Valerie King
University of Victoria; Member, School of Mathematics
April 1, 2014
Byzantine agreement is a fundamental problem of distributed computing which involves coordination of players when a constant fraction are controlled by a malicious adversary. Each player starts with a bit, and the goal is for all good players to agree on a bit whose value is is equal to some good player's initial bit. I'll present the first algorithm with polynomial expected time in the asynchronous message-passing model with a strong adversary.