Attack-Resistant Algorithms for Massive Networks

August 14, 2006
Jared Saia | University of New Mexico

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).

Speaker Details

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), and the number of citations to his papers is now well over 300. He has secured about half a million dollars in funding in grants from NSF and Sandia Labs and has served on the program committee for PODC for the last two years. So far, he has graduated 1 PhD student and 5 Masters students.