Structured Overlay without Consistent Hashing: Empirical Results
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Consistent hashing is at the core of many P2P protocols. It evenly distributes the keys over the nodes, thereby enabling logarithmic routing effort 'with high probability'. However, consistent hashing incurs unnecessary overhead as shown in this paper. By removing consistent hashing from Chord, we derived a protocol that has the same favorable logarithmic routing performance but needs less network hops for updating its routing table. Additionally, our Chord# protocol supports range queries, which are not possible with Chord. Our empirical results indicate that Chord# outperforms Chord even under high churn, that is, when nodes frequently join and leave the systemKeywords
This publication has 10 references indexed in Scilit:
- Skip graphsACM Transactions on Algorithms, 2007
- MercuryPublished by Association for Computing Machinery (ACM) ,2004
- Enabling flexible queries with guarantees in p2p systemsIEEE Internet Computing, 2004
- Simple efficient load balancing algorithms for peer-to-peer systemsPublished by Association for Computing Machinery (ACM) ,2004
- Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer SystemsPublished by Elsevier ,2004
- Scalable, efficient range queries for grid information servicesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- KingPublished by Association for Computing Machinery (ACM) ,2002
- ChordACM SIGCOMM Computer Communication Review, 2001
- A scalable content-addressable networkPublished by Association for Computing Machinery (ACM) ,2001
- Consistent hashing and random treesPublished by Association for Computing Machinery (ACM) ,1997