Wednesday, April 10th, 2013 | 4pm-5pm | Burnside 1205 |

Department of Computer Science, University of Victoria

Byzantine Fault Tolerance and Weak Random Sources

Distributed computing concerns the coordination of processors in order to share resources or coordinate a response, typically where some processors are assumed faulty. In the Byzantine model, the faults are of the worst kind; a constant fraction of processors (whose identities are unknown to the algorithm) may be controlled by a malicious adversary. Coordination is achieved through the passing of messages between pairs of processors. Two problems in this model are leader election and Byzantine agreement. The former is to bring processors to agreement on a good processor. The latter assumes each processor starts with a private bit; the goal is to bring processors to agreement on the value of such a bit. This talk will survey some of the challenges Jared Saia and I and others have addressed in order to deal this model. I will cover the connection between this model and results on weak random sources, sources which generate a mix of random and adversarily fixed bits. I will also give a high level view of our most recent result which solves a 30-year old problem: Can Byzantine agreement be solved in less than exponential time in an asynchronous model with an adversary which has access to the entire state of all the processors? I will show the connection of this problem to the computational problem of finding a planted clique-like subgraph in a random graph.