Princeton DIMACS Theory Lunch Seminar


"Polynomial-time Byzantine agreement for n>3t processors in t+1 rounds"


Yoram Moses
Weizmann Institute


Room 402, Computer Science Building
Princeton University


12 Noon
Tuesday, April 11, 1995


This talk will describe a polynomial-time protocol for reaching Byzantine agreement in $t+1$ rounds whenever $n>3t$, where~$n$ is the number of processors and~$t$ is an {\it a priori} upper bound on the number of failures. This resolves an open problem presented by Pease, Shostak and Lamport in 1980. The talk will be self-contained, and will focus on the main ideas in the solution. This is joint work with Juan Garay.
Document last modified on April 11, 1995