Choosing a random peer
- 25 July 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 125-130
- https://doi.org/10.1145/1011767.1011786
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 networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Routing networks for distributed hash tablesPublished by Association for Computing Machinery (ACM) ,2003
- A stochastic process on the hypercube with applications to peer-to-peer networksPublished by Association for Computing Machinery (ACM) ,2003
- Novel architectures for P2P applicationsPublished by Association for Computing Machinery (ACM) ,2003
- Simple Load Balancing for Distributed Hash TablesPublished by Springer Nature ,2003
- ViceroyPublished by Association for Computing Machinery (ACM) ,2002
- Finding nearest neighbors in growth-restricted metricsPublished by Association for Computing Machinery (ACM) ,2002
- ChordPublished by Association for Computing Machinery (ACM) ,2001
- Randomized AlgorithmsPublished by Cambridge University Press (CUP) ,1995
- Random oracles are practicalPublished by Association for Computing Machinery (ACM) ,1993