Events & News
Colloquium
| Category | Lecture |
| Date | Thursday, January 26, 2012 |
| Time | 11:00 am |
| Concludes | 12:00 pm |
| Location | Gould-Simpson 906 |
| Speaker | Jared Saia |
| Title | Associate Professor |
| Affiliation | University of New Mexico |
Conflict on Large Networks
This talk will describe several recent results on designing robust algorithms for large networks. First, we consider the Byzantine agreement problem, which asks: Can a set of agents agree on a value, even if some of the agents are not trustworthy? We describe an algorithm to solve this problem that is scalable in the sense that it requires each agent to send only O(sqrt(n)) bits, where n is the number of agents. To the best of our knowledge, our results on this problem are the first that solve Byzantine agreement without requiring all-to-all communication.
Next, we consider a problem where Alice wants to send a message to Bob along a channel and Carol wants to prevent this. Each player can either send, listen or block the channel in any time step for some small, fixed cost. We describe an algorithm that ensures that if Carol spends B dollars, Bob receives the message, and Alice and Bob spend only O(B^(phi -1) + 1) = O(B^.62 + 1) dollars, where phi is the golden ratio. We generalize this result to many players, and describe applications in mitigating denial-of-service attacks.
Finally, we describe an algorithm that enables self-healing in an overlay network, even when an omniscient adversary repeatedly removes carefully chosen nodes. Specifically, the algorithm ensures that the shortest path between any pair of nodes never increases by more than a logarithmic factor, and that the degree of any node never increases by more than a factor of 3.
The first half of the talk will cover the scalable Byzantine agreement result in some detail, while the remainder of the talk will outline the second and third results. The paper on the scalable Byzantine agreement result won the best paper award at PODC 2010.
Biography
Jared Saia obtained his PhD from the University of Washington and is now an Associate Professor at the University of New Mexico. His broad research interests are in theory and algorithms with strong interests in distributed algorithms, security, game theory, and probabilistic methods. A general interest is determining how large groups can function effectively even when there is no leader. He is the recipient of the NSF CAREER Award, the School of Engineering Junior Faculty Research Excellence Award, and several best paper awards.