Choosing a random peer
Authors:
Open Access
- 25 July 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 125-130
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(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.Keywords
This publication has 10 references indexed in Scilit:
- Random walks in peer-to-peer networks2004
- Routing networks for distributed hash tables2003
- A stochastic process on the hypercube with applications to peer-to-peer networks2003
- Novel architectures for P2P applications2003
- Simple Load Balancing for Distributed Hash Tables2003
- Viceroy2002
- Finding nearest neighbors in growth-restricted metrics2002
- Chord2001
- Randomized Algorithms1995
- Random oracles are practical1993