[Speaker]: Seth Gilbert (EPFL)
[Title]: Simple Distributed Agreement with Optimal Communication Complexity
[Date]: Oct. 14th (Wed)
[Time]: 3PM - 4:50PM
[Place]: TBA

[Abstract]:
We consider the problem of fault-tolerant agreement in a crash-prone
synchronous system.  There are two standard metrics for evaluating an
agreement protocol: time complexity and communication complexity.  In
this talk, I will focus on the latter, showing how to achieve
agreement using only O(n) bits of communication (with high
probability), in O(log n) time.

The key technique that makes this possible is "universe reduction:" we
delegate the task of agreement to a small committee, yielding a very
efficient protocol.  The most expensive part of the protocol, in fact,
is disseminating the result of the computation to non-committee
members.  An incidental benefit of this technique is that it yields a
protocol that is quite simple.  (In applying the idea of "universe
reduction" to agreement protocols, we are following the path pioneered
by Ben-Or, Pavlov, and Vaikuntanathan [2006], and also Kapron, Kempe,
King, Saia, and Sanwalani [2008], among others.)

While the protocol, as described in this talk, is designed for
synchronous networks, it can be modified to cope with partial
synchrony.  The same techniques also can be used to implement a
randomized gossip protocol that terminates in O(log*n) rounds using
O(n) messages (with bit complexity that depends on the data being
gossiped).  Joint work with Dariusz Kowalski.