Recent News
Inaugural School of Engineering Teaching Innovation Fellows selected
February 2, 2024
UNM computer scientist wins NSF CAREER Award to optimize supercomputer performance
February 1, 2024
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
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.