Byzantine Agreement in the Clear
COM1 Level 2
SR1, COM1-02-06
This is a distinguished talk as part of the NUS Computer Science Research Week 2019 (http://researchweek.comp.nus.edu.sg).
Abstract:
Forty 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 for an asynchronous network: an impossibility result for any deterministic scheme, a randomized exponential time algorithm, and a demonstration that one globally known coin toss could solve the problem in constant expected time. Some researchers turned to the use of committed secret coinflips via cryptography, while others turned to the study of collective coin flipping with full information.
Interest in Byzantine agreement has risen in recent years with the development of distributed ledgers, like bitcoin. In this talk I'll survey some communication-efficient techniques for Byzantine agreement in the clear, and consider how they relate to distributed ledger systems. Such techniques avoid the overhead of cryptographic techniques and assumptions about limits on the computational power of adversaries. In particular, I'll include a description of the first polynomial time algorithm for Byzantine Agreement in an asynchronous model, which is obtained by solving a new collective coin flipping problem.
The talk starts with a tutorial on the preliminaries and the theoretical foundations of this topic.
Biodata:
Valerie King is Professor in the Department of Computer Science at the University of Victoria, in BC, Canada. She received her PhD in computer science from the University of California, Berkeley under the supervision of Richard Karp, and a JD from UC Berkeley School of Law. She was a postdoctoral fellow at the University of Toronto under Faith Ellen and at Princeton under Andrew CC Yao. She was a visiting professor at Hebrew University, University of Copenhagen, University of Toronto, UC Berkeley, and Ecole Normale Superieur in Paris. Her industrial research experience includes Microsoft Research (SVC), Compaq and HP Systems Research Center in Palo Alto, and NECI in Princeton. In addition she was a member of the Institute for Advanced Study in Princeton and the Simons Institute in Berkeley. Her recent service includes membership in the Independent Panel on Internet Voting for Elections BC and PC chair of STOC 2017. In 2014, she received the distinction ACM Fellow for her work on randomized algorithms, especially dynamic graph algorithms and Byzantine fault tolerant distributed computing.