Professor Valerie King, University of Victoria
Abstract: Over 35 years ago, Leslie Lamport formulated a fundamental problem of coordination in a distributed network. He asked us to imagine an army led by generals, who send messages to each other with the goal of coming to agreement on a strategy. Planted among those generals are spies who seek to thwart this goal. Not long after this Byzantine agreement problem was presented, there were a few developments: an impossibility for any deterministic scheme in an asynchronous scheme, a randomized exponential time algorithm, and a scheme which used one globally known coin toss to solve the problem in constant expected time.
Some researchers turned to the use of committed secret coinflips via cryptography to solve Byzantine agreement, and/or they assumed a form of bounded asynchrony (as in last week’s talk). Other researchers focussed on the problem of collective coin flipping in order to prove lower bounds.
A few years ago, Jared Said and I developed the first polynomial time algorithm for Byzantine agreement in a fully asynchronous model, which is obtained by solving a new collective coin flipping problem. Recently my student Nick Benson has reduced the resilience and time for this algorithm. I’ll describe these results and the coin flipping problem.