Distributed Line Graphs: A Universal Technique for Designing DHTs Based on Arbitrary Regular Graphs
Authors:
- 20 December 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 24 (9) , 1556-1569
Abstract
Most proposed DHTs engage certain topology maintenance mechanisms specific to the static graphs on which they are based. The designs of these mechanisms are complicated and repeated with graph-relevant concerns. In this paper, we propose the distributed line graphs (DLG), a universal technique for designing DHTs based on arbitrary regular graphs. Using DLG, the main features of the initial graphs are preserved, and thus people can design a new DHT by simply choosing the graph with desirable features and applying DLG to it. We demonstrate the power of DLG by illustrating four DLG-enabled DHTs based on different graphs, namely, Kautz, de Bruijn, butterfly, and hypertree graphs. The effectiveness of our proposals is demonstrated through analysis, simulation, and implementation.Keywords
This publication has 25 references indexed in Scilit:
- SKY: efficient peer-to-peer networks based on distributed Kautz graphsScience China Information Sciences, 2008
- HyperTree for self-stabilizing peer-to-peer systemsDistributed Computing, 2007
- Novel architectures for P2P applicationsACM Transactions on Algorithms, 2007
- D2B: A de Bruijn based content-addressable networkTheoretical Computer Science, 2006
- Tapestry: A Resilient Global-Scale Overlay for Service DeploymentIEEE Journal on Selected Areas in Communications, 2004
- On the Fundamental Tradeoffs Between Routing Table Size and Network Diameter in Peer-to-Peer NetworksIEEE Journal on Selected Areas in Communications, 2004
- A stochastic process on the hypercube with applications to peer-to-peer networks2003
- Chord: a scalable peer-to-peer lookup protocol for internet applicationsIEEE/ACM Transactions on Networking, 2003
- Koorde: A Simple Degree-Optimal Distributed Hash Table2003
- The partial line digraph technique in the design of large interconnection networksIEEE Transactions on Computers, 1992