Byzantine Agreement in Expected Polynomial Time

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. A strong adversary in the asynchronous model may corrupt players adaptively, may schedule message delivery with arbitrarily long delays unknown to the players, and has full knowledge of the state of all players. Ben-Or's 1983 expected exponential time algorithm reduced the problem to a series of iterations in which the players attempt to agree on a global coinflip using their private coinflips. In our algorithm, players use the history of observed coinflips to individually detect statistically deviant behavior by adversarily controlled players, so as to eventually disregard their inputs to arrive at a global coinflip. No knowledge of distributed computing will be assumed. One of my goals is to give a characterization of the model which is easy for non-experts to reason about. This is joint work with Jared Saia.