Symmetric Replication for Structured Peer-to-Peer Systems
Number of Authors: 3
2005 (English)Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
2005, 1. , 12 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-21109OAI: oai:DiVA.org:ri-21109DiVA: diva2:1041143
The 3rd International Workshop on Databases, Information Systems and Peer-to-Peer Computing