Byzantine Agreement October 9, 2007

Favorite:

Google Tech Talks
August 3, 2007

ABSTRACT

Byzantine Agreement is a fundamental problem in distributed computing, that is--design a protocol to bring processors to agreementon a bit despite a fraction of bad processors behaving to disrupt the outcome. First proposed in 1980, it was proved impossible to solve deterministically which launched some of the early work on randomized algorithms. As the only (randomized) solutions for synchronous and asynchronous environments were resp., nearly linear time or exponential time, or required assumptions of private channels, this spurred the field of cryptography to develop concepts like multiparty secure computation.

We have designed a distributed...