News Archives

Secure Algorithms and Data Structures for Massive Networks

September 15, 2005

  • Date: Thursday, September 15, 2005 
  • Time: 11:00-12:15pm.
  •  Place: Woodward 149

Prof. Jared Saia
Department of Computer Science University of New Mexico

In this talk, we will present results on designing algorithms and data structures which are distributed, scalable and robust to adversarial attack. The first part of the talk will describe a robust distributed hash table (DHT), based on the popular DHT, Chord. This new DHT, is robust with high probability for any time period during which: 1) there are always at least z total peers in the network for some integer z; 2) there are never more than (1/4-ε)z bad peers in the network for a fixed ε>0; and 3) the number of peer insertion and deletion events is no more than zk for some tunable parameter k. We assume there is an adversary controlling the bad peers and that the IP-addresses of all the bad peers and the locations where they join the network are carefully selected by this adversary. In comparison to Chord, the resources required by our new DHT are only a polylogarithmic factor greater in communication, messaging, and linking costs.

The second part of the talk will describe a new scalable algorithm for the leader election problem. In the leader election problem, there are n processors of which (1-b) n are good for some b>0. The problem is to design a distributed protocol to elect a good leader from the set of all processors. I will describe a new, leader election protocol that is scalable in the sense that each good processor sends and processes a number of bits which is only polylogarithmic in n. For b < 1/3, our protocol elects a good leader with constant probability and ensures that a 1-o(1) fraction of the good processors know this leader. To the best of our knowledge, this is the first leader election algorithm which ensures that each good processor sends and processes a sublinear number of bits. This result can be used to provide scalable solutions to Byzantine agreement and other problems.

This is joint work with Amos Fiat (U. Tel Aviv), Valerie King (U. Victoria), Erik Vee (IBM Labs), Maxwell Young (U. New Mexico) and Vishal Sanwalani (U. New Mexico) and represents work previously published in PODC and ESA.