Recent News
Hand and Machine Lab’s Experimental Clay Exhibition closing celebration Nov. 17
November 15, 2023
Moses selected as special assistant to the dean for educational initiatives
October 3, 2023
Computer science student navigates crime’s depths with AI at Department of Homeland Security internship
August 25, 2023
UNM researchers take a deep dive into our changing planet with SIMReef project
August 1, 2023
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.