Recent News
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
‘A serendipitous life’: The right people in the right places were key to Lydia Tapia’s success
September 9, 2022
Time-tested: Computer scientist’s research honored for its impact after a decade
August 17, 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.
