Symmetric Replication for Structured Peer-to-Peer Systems

Ghodsi, Ali and Onana Alima, Luc and Haridi, Seif (2005) Symmetric Replication for Structured Peer-to-Peer Systems. In: The 3rd International Workshop on Databases, Information Systems and Peer-to-Peer Computing, July 2005, Trondheim, Norway.



Structured peer-to-peer systems rely on replication as a basic means to provide fault-tolerance in presence of high churn. Most select replicas using either multiple hash functions, successor-lists, or leaf-sets. We show that all three alternatives have limitations. We present and provide full algorithmic speci¯cation for a generic replication scheme called symmetric replication which only needs O(1) message for every join and leave operation to maintain any replication degree. The scheme is applicable to all existing structured peer-to-peer systems, and can be implemented on-top of any DHT. The scheme has been implemented in our DKS system, and is used to do load-balancing, end-to-end fault-tolerance, and to increase the security by using distributed voting. We outline an extension to the scheme, implemented in DKS, which adds routing proximity to reduce latencies. The scheme is particularly suitable for use with erasure codes, as it can be used to fetch a random subset of the replicas for decoding.

Item Type:Conference or Workshop Item (Paper)
ID Code:247
Deposited By:DSL Researcher
Deposited On:27 Jan 2006
Last Modified:18 Nov 2009 15:55

Repository Staff Only: item control page