Recent News
Computer science student chosen for Churchill Scholarship
January 11, 2023
Leaving a legacy: Computer science professor’s research honored with Test of Time Award
December 9, 2022
Virtual workshop on climate-driven extreme events planned Nov. 10
October 25, 2022
MathWorks gives $2 million to UNM to create endowed chair for Department of Computer Science
October 18, 2022
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).