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(log n) messages in expectation for a DHT like Chord [17]. 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.
No takes yet. Share an insight, caveat, or question.
King et al. (2004) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: