The Taub Faculty of Computer Science Events and Talks

Byzantine agreement is a fundamental problem of distributed computing which involves coordination of processors when a constant fraction are controlled by a malicious adversary.

I'll present the first algorithm with polynomial expected time in the asynchronous model where the adversary may corrupt processors adaptively and has full knowledge of the state of all processors.

Ben-Or's 1983 expected exponential time algorithm reduced the problem to a series of iterations in which individual processors attempt to agree on a global coinflip from their private coinflips. In our algorithm, processors use the history of observed coinflips to individually detect statistically deviant behavior by adversarily controlled processors, so as to eventually disregard their inputs to the global coinflip routine.

We reduce the global coinflip problem to a (non-distributed) computation problem on a sequence of matrices with some entries randomly generated and others fixed by the adversary which must ensure a certain property of the matrix, yet remain hidden from the algorithm. We give a simple spectral technique for solving this problem in polytime and polynomial number of iterations, yielding a Byzantine agreement protocol with expected polynomial computation and communication time.

No knowledge of distributed computing will be assumed.