Recent News
Angel receives 2022 ACM SIGGRAPH Distinguished Educator Awar
August 15, 2022
At Hand and Machine Lab event, art was a two-way interactive experience
June 2, 2022
Computer science changed UNM grad’s tune on a career
May 18, 2022
Computer science graduate student to compete in climbing world championships in May
April 26, 2022
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.