News Archives

Attack-Resistant Algorithms for Massive Networks

September 22, 2006

Watch Colloquium: 

Quicktime (157 Meg) 
Part One, AVI (201 Meg)
Part Two, AVI (221 Meg)
Question and answers, AVI, 15 frames per second (128 Meg)


  • Date: Friday, September 22, 2006 
  • Time: 1 pm — 2:15 pm 
  • Place: ME 218

Jared Saia 
Department of Computer Science, UNM

Abstract: In this talk, we will describe new attack-resistant algorithms for peer-to-peer networks. Our attack model is rather strong in that we assume that an omniscient and computationally unbounded adversary takes over up to a constant fraction of the peers in the network. Our algorithms are scalable in the sense that for every peer, all major resource costs (e.g. latency, number of bits sent and received, number of links to other peers) are polylogarithmic in the number of peers in the network. We present attack-resistant algorithms for the problems of leader election, Byzantine agreement and voting and describe a general framework that can be used to design such algorithms for other types of problems. We also describe many areas for future work.

These results are joint with Valerie King (U. Victoria), Vishal Sanwalani (U. Waterloo) and Erik Vee (IBM Labs), and describe work previously published in the Symposium of Discrete Algorithms (SODA), and that will appear in Foundations of Computer Science (FOCS).

Bio Jared Saia obtained his PhD in Computer Science at the University of Washington in 2002 under Anna Karlin and is now an Assistant Professor at the University of New Mexico. His broad research interests are in theory and algorithms with a strong focus on designing provably good distributed algorithms for large-scale networks. He has published in a wide variety of the top conferences and journals in this area including: Foundations of Computer Science (FOCS), Principles of Distributed Computing (PODC), and Symposium on Discrete Algorithms (SODA).