Comparing the Performance of Distributed Hash Tables Under Churn
Lecture notes in computer sciencePublished 1 January 2005
Jinyang Li, Jeremy Stribling, Thomer M. Gil, Robert Morris, M. Frans Kaashoek
Citations215
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A unified framework for evaluating cost and performance of DHT parameters is formulates, which correctly accounts for background maintenance traffic and timeouts during lookup due to stale routing data, and also correctly leaves open the possibility of different preferences in the tradeoff of lookup time versus communication cost.
Abstract
A protocol for a distributed hash table (DHT) incurs communication costs to keep up with churn – changes in membership – in order to maintain its ability to route lookups efficiently. This paper formulates a unified framework for evaluating cost and performance. Communication costs are combined into a single cost measure (bytes), and performance benefits are reduced to a single latency measure. This approach correctly accounts for background maintenance traffic and timeouts during lookup due to stale routing data, and also correctly leaves open the possibility of different preferences in the tradeoff of lookup time versus communication cost. Using the unified framework, this paper analyzes the effects of DHT parameters on the performance of four protocols under churn.
Keywords
Computer Science
Chord
9,645 Citations2001Ion Stoica, Robert Morris +3 more
Results from theoretical analysis, simulations, and experiments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
Lecture notes in computer sciencePastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems
7,296 Citations2001Antony Rowstron, Peter Druschel
Experimental results obtained with a prototype implementation on an emulated network of up to 100,000 nodes confirm Pastry's scalability and efficiency, its ability to self-organize and adapt to node failures, and its good network locality properties.
IEEE/ACM Transactions on NetworkingChord: a scalable peer-to-peer lookup protocol for internet applications
3,122 Citations2003Ion Stoica, Robert Morris +5 more
Results from theoretical analysis and simulations show that Chord is scalable: Communication cost and the state maintained by each node scale logarithmically with the number of Chord nodes.
Lecture notes in computer scienceKademlia: A Peer-to-Peer Information System Based on the XOR Metric
3,000 Citations2002Petar Maymounkov, David Mazières
A peer-to-peer distributed hash table with provable consistency and performance in a fault-prone environment is described using a novel XOR-based metric topology that simplifies the algorithm and facilitates the proof.
IEEE Journal on Selected Areas in CommunicationsTapestry: A Resilient Global-Scale Overlay for Service Deployment
1,726 Citations2004Bi Zhao, Ling Huang +4 more
Experimental results show that Tapestry exhibits stable behavior and performance as an overlay, despite the instability of the underlying network layers, illustrating its utility as a deployment infrastructure.
Handling churn in a DHT
851 Citations2004Sean Rhea, Dennis Geels +2 more
Viceroy
637 Citations2002Dahlia Malkhi, Moni Naor +1 more
This work proposes a family of constant-degree routing networks of logarithmic diameter, with the additional property that the addition or removal of a node to the network requires no global coordination, only a constant number of linkage changes in expectation, and a logarithmic number with high probability.
ACM SIGCOMM Computer Communication ReviewKing
629 Citations2002Krishna P. Gummadi, Stefan Saroiu +1 more
The accuracy of King is significantly better than the accuracy of IDMaps, and that King tends to preserve order among its latency estimates, as well as a variety of measurement studies and applications that could benefit from the tool.
The impact of DHT routing geometry on resilience and proximity
572 Citations2003Krishna P. Gummadi, R. Gummadi +4 more
The basic finding is that, despite the initial preference for more complex geometries, the ring geometry allows the greatest flexibility, and hence achieves the best resilience and proximity performance.
Lecture notes in computer scienceKoorde: A Simple Degree-Optimal Distributed Hash Table
567 Citations2003M. Frans Kaashoek, David R. Karger
Koorde is a new distributed hash table (DHT) based on Chord 15 and the de Bruijn graphs 2 that meets various lower bounds, such as O(log n) hops per lookup request with only 2 neighbors per node.
Communications of the ACMPeer-to-peer systems
562 Citations2010Rodrigo Rodrigues, Peter Druschel
Within a decade, P2P has proven to be a technology that enables innovative new services and is used by millions of people every day.
Analysis of the evolution of peer-to-peer systems
409 Citations2002David Liben‐Nowell, Hari Balakrishnan +1 more
It is argued that traditional performance measures based on run-time are uninformative for a continually running P2P network, and that the rate at which nodes in the network need to participate to maintain system state is a more useful metric.
Multimedia SystemsMeasuring and analyzing the characteristics of Napster and Gnutella hosts
385 Citations2003Stefan Saroiu, Krishna P. Gummadi +1 more
A detailed measurement study of the two popular peer-to-peer file sharing systems, namely Napster and Gnutella, shows that there is significant heterogeneity and lack of cooperation across peers participating in these systems.
King
370 Citations2002Krishna P. Gummadi, Stefan Saroiu +1 more
The accuracy of King is significantly better than the accuracy of IDMaps, and that King tends to preserve order among its latency estimates, as well as a variety of measurement studies and applications that could benefit from the tool.
Lecture notes in computer scienceKelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead
284 Citations2003Indranil Gupta, Ken Birman +3 more
This paper explores a new point in design space in which increased memory usage and constant background communication overheads are tolerated to reduce file lookup times and increase stability to failures and churn.
Lecture notes in computer sciencePeer-to-Peer Systems II
246 Citations2003M. Frans Kaashoek, Ion Stoica
ACM SIGCOMM Computer Communication ReviewA measurement study of Napster and Gnutella as examples of peer-to-peer file sharing systems
191 Citations2002Krishna P. Gummadi, Stefan Saroiu +1 more
An extensive measurement study of Napster and Gnutella is presented and analyzed to present and analyze their relationship to music piracy.
Performance and dependability of structured peer-to-peer overlays
187 Citations2004Miguel Castro, M. Costa +1 more
This paper presents techniques that continuously detect faults and repair the overlay to achieve high dependability and good performance in realistic environments and shows that previous concerns about the performance and dependability are unfounded.
One hop lookups for peer-to-peer overlays
132 Citations2003Anjali Gupta, Barbara Liskov +1 more
This paper shows that this assumption is unnecessary, and presents a technique that maintains complete routing tables at each node, and is able to handle frequent membership changes and scales to large systems having more than a million nodes.
On the fundamental tradeoffs between routing table size and network diameter in peer-to-peer networks
58 Citations2004Jun Xu
A new routing algorithm is proposed that reduces the routing table size and the network diameter of Chord both by 21.4% without introducing any other protocol overhead, based on a novel number-theoretical technique.
Lecture notes in computer scienceStructured Peer-to-Peer Overlays Need Application-Driven Benchmarks
17 Citations2003Sean Rhea, Timothy Roscoe +1 more
The case for developing application-driven benchmarks for structured peer-to-peer overlays is presented, a model of the services they provide applications is given, and the results of two preliminary benchmarks are described and presented.