News Archives

Choosing a Random Peer

September 9, 2004

Date: Thursday September 9, 2004
Time: 11am-12:15pm
Location: Woodward 149


Jared Saia <saia@cs.unm.edu>
Department of Computer Science University of New Mexico

Abstract: We present the first fully distributed algorithm which chooses a peer uniformly at random from the set of all peers in a distributed hash table (DHT). Our algorithm has latency $O(\log n)$ and sends $O(\logn)$ messages in expectation for a DHT like Chord. Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods; to provide support for randomized, distributed algorithms over peer-to-peer networks; and to support the creation and maintenance of random links, and thereby offer a simple means of improving fault-tolerance. This is joint work with Valerie King which appeared in PODC 2004.