News Archives

[Colloquium] Emergent Reliability: Recent Results in Byzantine Agreement

September 28, 2012

Watch Colloquium: 

M4V file (607 MB)

  • Date: Friday, September 28, 2012 
  • Time: 12:00 pm — 12:50 pm 
  • Place: Centennial Engineering Center 1041

Jared Saia
Department of Computer Science University of New Mexico 

Imagine we have a collection of agents, some of which are unreliable, and we want to build a reliable system. This fundamental problem is faced by many natural systems like social insect colonies, the brain and the immune system. A key component of these systems is that periodically all agents commit to a particular action. The Byzantine agreement problem formalizes the challenge of commitment by asking: Can a set of agents agree on a value, even if some of the agents are unreliable? Application areas of Byzantine agreement include: control systems, distributed databases, peer-to-peer systems, mechanism design, sensor networks, and trust management systems.

In this talk, we describe several recent results in Byzantine agreement. First, we describe an algorithm for Byzantine agreement that is scalable in the sense that each agent sends only O(sqrt(n)) bits, where n is the total number of agents. Second, we describe very efficient algorithms to solve Byzantine agreement in the case where all agents have access to a global coin. Finally, we describe a very recent result that gives an algorithm to solve Byzantine agreement in the presence of an adversary that is adaptive: the adversary can take over up to a third of the agents at any point during the execution of the algorithm. Our algorithm runs in expected polynomial time and is the first sub-exponential algorithm in this model.

 

Bio: Jared Saia is an Associate Professor of Computer Science at the University of New Mexico. His broad research interests are in theory and algorithms with a focus on designing distributed algorithms that are robust against a computationally unbounded adversary. He is the recipient of several grants and awards including an NSF CAREER award, School of Engineering Senior and Junior Faculty Research Excellence awards, and several best paper awards.