Dr. Carles Pairot's Distributed Hash Tables Links

For more links on my other research topics, click here.


 CAN (Content-Addressable Network)

A Scalable Content-Addressable Network. Ratnasamy, S.; Francis, P.; Handley, M; et al. In this paper, the concept of a Content-Addressable Network (CAN) is introduced as a distributed infrastructure that provides hash table-like functionality on Internet-like scales.


Analysis of the Evolution of Peer-to-Peer Systems. Liben-Nowell, D.; Balakrishnan, H. and Karger, D. In this paper, a theoretical analysis of peer-to-peer networks operating in the face of concurrent joins and unexpected departures is given.

Serving DNS using a Peer-to-Peer Lookup Service. Cox, R.; Muthitacharoen, A. and Morris, R.T. The DNS security extensions (DNSSEC) allow verification of records obtained by alternate means, opening exploration of alternative storage systems for DNS records. We explore one alternative using DHash, a peer-to-peer distributed hash table built on top of Chord.

Observations on the Dynamic Evolution of Peer-to-Peer Networks. Liben-Nowell, D.; Balakrishnan, H. and Karger, D. A fundamental challenge in peer-to-peer systems is proving statements about the evolution of the system while nodes are continuously joining and leaving.

Security Considerations for Peer-to-Peer Distributed Hash Tables. Sit, E. and Morris, R.T. This paper looks at what sorts of security problems are inherent in large peer-to-peer systems based on distributed hash lookup systems.

Wide-area cooperative storage with CFS. Dabek, F.; Kaashoek M.F.; Karger, D.; et al. The Cooperative File System (CFS) is a new peer-to-peer read-only storage system that provides provable guarantees for the efficiency, robustness, and load-balance of file storage and retrieval.

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. Stoica, I.; Morris, R.; Karger, D.; et al. A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that addresses this problem.

Building Peer-to-Peer Systems with Chord, a Distributed Lookup Service. Dabek, F.; Brunskill, E.; Kaashoek, M.F.; et al. The core problem facing peer-to-peer systems is locating documents in a decentralized network and propose Chord, a distributed lookup primitive. Chord provides an efficient method of locating documents while placing few constraints on the applications that use it.

The Circle

The Circle: one ring, no rulers. The Circle is an open source scalable decentralized peer-to-peer application. The Circle is written in Python and it runs on Linux and Windows. At the core of the Circle is a decentralized hash table, or "Chord". Very interesting PDF slides available here.

 GISP (Global Information Sharing Protocol)

GISP provides a distributed hash table built on top of the JxTA platform. Developed by Daishi Kato it features scalability, simplicity, and easiness of development.

A Distributed Index for Peer-to-Peer Systems. Kato, D. This paper proposes GISP, which aims at a world-wide distributed index. By building GISP on top of JxTA, a peer could reach a peer behind a firewall and even a peer in a different network transport.


Kademlia web site. Contains theory and practice sections.

Kademlia: A Peer-to-peer Information System Based on the XOR Metric. Maymounkov, P. and Birman, K. A peer-to-peer system which has proven consistency and performance in a fault-prone environment is described. Kademlia routes queries and locates nodes using a novel XOR-based metric topology that simplifies the algorithm and facilitates our proof.

eMule Kademlia Test Client. An eMule client using Kademlia overlay to provide Overnet compatibility.


Khashmir is a Distributed Hash Table (DHT) based on Kademlia and written in Python. Created by Aaron Swartz.


MLDonkey is compatible with Overnet (non-open source implementation of Kademlia developed by MetaMachine), and Overnet claims that it does Kademlia and multisource downloading. It supports multiple P2P networks, including eDonkey, Overnet, Bittorrent, Gnutella (Bearshare, Limewire, etc), Gnutella2 (Shareaza), Fasttrack (KaZaA, iMesh, Grobster), Soulseek, Direct Connect, and OpenNap.


SharkyPy is an implementation of a Kademlia Distributed Hash Table. The source is written by Heiko Wundram and released under the LGPL.

 Pastry, Scribe, PAST, ...


Security for structured peer-to-peer overlay networks. Castro, M.; Druschel, P.; Ganesh, A.; et al. Current overlays are not secure; even a small fraction of malicious nodes can prevent correct message delivery throughout the overlay. This paper studies attacks aimed to preventing correct message delivery in structured peer-to-peer overlays and presents defenses to these attacks.

One ring to rule them all: Service discovery and binding in structured peer-to-peer overlay networks. Castro, M.; Druschel, P.; Kermarrec, A.M.; et al. One major problem with existent DHT systems is how to bootstrap them. In this position paper, the design of an infrastructure that uses a universal overlay to provide scalable infrastructure to bootstrap multiple service overlays is sketched.

Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. Rowstron, A. and Druschel, P. This paper presents the design and evaluation of Pastry, a scalable, distributed object location and routing substrate for wide-area peer-to-peer applications.

Scalable Application-level Anycast for Highly Dynamic Groups. Castro, M.; Druschel, P.; Kermarrec, A.M.; et al. An application-level implementation of anycast for highly dynamic groups is presented.


An Evaluation of Scalable Application-level Multicast Built Using Peer-to-peer overlays. Castro, M; Jones, M.B.; Kermarrec, A.M.; et al. This paper reports the first head-to-head comparison of CAN-style versus Pastry-style overlay networks, using multicast communication workloads running on an identical simulation infrastructure.

Scribe: A large-scale and decentralised application-level multicast infrastructure. Castro, M.; Druschel, P.; Kermarrec, A.M. This paper presents Scribe, a scalable application-level multicast infrastructure. Scribe supports large numbers of groups, with potentially large numbers of members per group.


PAST: A large-scale, persistent peer-to-peer storage utility. Druschel, P. and Rowstron, A. This paper sketches the design of PAST, a large-scale, Internet-based, global storage utility that provides scalability, high availability, persistence and security.


SplitStream: High-bandwidth multicast in a cooperative environment. Castro, M.; Druschel, P; Kermarrec, A.M.; et al. In tree-based multicast systems, a relatively small number of interior nodes carry the load of forwarding multicast messages. This works well when the interior nodes are highlyavailable, dedicated infrastructure routers but it poses a problem for application-level multicast in peer-to-peer systems. SplitStream addresses this problem by striping the content across a forest of interior-node-disjoint multicast trees that distributes the forwarding load among all participating peers.

 Tapestry, Bayeux, OceanStore, ...


Optimizations for Locality-Aware Structured Peer-to-Peer Overlays. Stribling, J.; Hildrum, K. and Kubiatowicz, J. Several optimizations aimed at improving the object location performance of locality-aware structured peer-to-peer overlays are presented.

Exploiting Routing Redundancy via Structured Peer-to-Peer Overlays. Zhao, B.Y.; Huang, L.; Stribling, J.; et al. In this paper, we present two adaptive mechanisms for structured overlays and illustrate their operation in the context of Tapestry, a fault-resilient overlay from Berkeley. We also describe a transparent, protocol-independent traffic redirection mechanism that tunnels legacy application traffic through overlays.

Tapestry: A Resilient Global-scale Overlay for Service Deployment. Zhao, B.Y.; Huang, L; Stribling, J.; et al. We present Tapestry, a peer-to-peer overlay routing infrastructure offering efficient, scalable, location-independent routing of messages directly to nearby copies of an object or service using only localized resources.

Distributed Object Location in a Dynamic Network. Hildrum, K.; Kubiatowicz, J.D.; Rao, S.; et al. A new distributed algorithm that can solve the nearest-neighbor problem for certain network topologies is presented.

Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Zhao, B.Y.; Kubiatowicz, J. and Joseph, A. Tapestry is an overlay location and routing infrastructure that provides location-independent routing of messages directly to the closest copy of an object or service using only point-to-point links and without centralized resources.


Bayeux: An Architecture for Scalable and Fault-tolerant Wide-Area Data Dissemination. Zhuang, S.Q.; Zhao, B.Y.; Joseph, A.D.; et al. In this paper, we propose Bayeux, an efficient application-level multicast system that scales to arbitrarily large receiver groups while tolerating failures in routers and network links.


Brocade: landmark routing on overlay networks. Zhao, B.Y.; Duan, Y.; Huang, L.; et al. In this paper, we propose a systemic design for a secondary overlay of super-nodes which can be used to deliver messages directly to the destination's local network, thus improving route efficiency.


OceanStore: An Architecture for Global-scale Persistent Storage. Kubiatowicz, J.; Bindel, D.; Chen, Y.; et al. OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is protected through redundancy and cryptographic techniques. To improve performance, data is allowed to be cached anywhere, anytime.


How to use the Tapestry overlay to implement Storm ?. A Tapestry and SEDA overview, including its APIs.


Viceroy: A Scalable and Dynamic Emulation of the Butterfly. Malkhi, D.; Naor, M. and Ratajczak, D. We propose 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, and only a constant number of linkage changes in expectation, and a logarithmic number with high probability.


Towards a Common API for Structured Peer-to-Peer Overlays. Dabek, F.; Zhao, B.Y.; Druschel, P.; et al. In this paper, we describe an ongoing effort to define common APIs for structured peer-to-peer overlays and the key abstractions that can be built on them. In doing so, we hope to facilitate independent innovation in overlay protocols, services, and applications, to allow direct experimental comparisons, and to encourage application development by third parties.

Sloppy hashing and self-organizing clusters. Freedman, M.J. and Mazières, D. We are building Coral, a peer-to-peer content distribution system. Coral creates self-organizing clusters of nodes that fetch information from each other to avoid communicating with more distant or heavily-loaded servers.

Koorde: A simple degree-optimal distributed hash table. Kaashoek, M.F. and Karger, D.R. Koorde1 is a new distributed hash table (DHT) based on Chord [15] and the de Bruijn graphs. While inheriting the simplicity of Chord, Koorde meets various lower bounds, such as O(log n) hops per lookup request with only 2 neighbors per node (where n is the number of nodes in the DHT), and O(log n/ log log n) hops per lookup request with O(log n) neighbors per node.

On Death, Taxes, and the Convergence of Peer-to-Peer and Grid Computing. Foster, I. and Iamnitchi, A.

Scooped, Again. Ledlie, J.; Shneidman, J.; Seltzer, M; et al. Very interesting paper focusing on the Grid an p2p features.

SOMO: Self-Organized Metadata Overlay for Resource Management in P2P DHT. Zhang, Z.; Shi, S.M. and Zhu, J. In this paper, we first describe the concept of data overlay, which is a mechanism to implement arbitrary data structure on top of any structured P2P DHT. With this abstraction, we developed a highly scalable, efficient and robust infrastructure, called SOMO, to perform resource management for P2P DHT.

On the Feasibility of Peer-to-Peer Web Indexing and Search. Li, J.; Loo, B.T.; Hellerstein, J.; et al. This paper discusses the feasibility of peer-to-peer full-text keyword search of the Web.

The Swan Project. Bonsma, E.; Hoile, C. SWAN (Small World Adaptive Networks) is a fully decentralised look-up system for Peer-to-Peer applications. In SWAN, information self-organises into a Small World Network, exploiting the principle of "six degrees of separation" to efficiently find resources without resorting to centralised look-up. The basic technology has been tested and is currently being built into serveral prototype applications, including iAnnotate and iLiftShare.

Efficient Broadcast in Structured P2P Networks. El-Ansary, S.; Alima, L.O.; Brand, P.; et al. In this position paper, we present an efficient algorithm for performing a broadcast operation with minimal cost in structured DHT-based P2P networks.

INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery. Balazinska, M.; Balakrishnan, H. and Karger, D. This paper describes the design, implementation, and evaluation of INS/Twine, an approach to scalable intentional resource discovery, where resolvers collaborate as peers to distribute resource information and to resolve queries.

Routing Algorithms for DHTs: Some Open Questions. Ratnasamy, S.; Shenker, S. and Stoica, I.

Locating Data in (Small-World?) Peer-to-Peer Scientific Collaborations. Iamnitchi, A; Ripeanu, M. and Foster, I.

Complex Queries in DHT-based Peer-to-Peer Networks. Harren, M.; Hellerstein, J.M.; Huebsch, R; et al. This paper outlines a research agenda for building complex query facilities on top of these DHT-based P2P systems. We describe the issues involved and outline our research plan and current status.

Efficient Peer-to-Peer Lookup Based on a Distributed Trie. Freedman, M.J. and Vingralek, R. Two main approaches have been taken for distributed key/value lookup operations in peer-to-peer systems: broadcast searches and location-deterministic algorithms. We describe a third alternative based on a distributed trie. This algorithm functions well in a very dynamic, hostile environment, offering security benefits over prior proposals.

A survey of implemented DHT overlays as of July 2003. Created by Hermanni Hyytiälä. Very interesting survey of many existent DHT overlays.

 This page was last updated on 08 September 2011. Carles Pairot - <carles.pairot@urv.cat>