Symmetrie Replication for Structured Peer-to-Peer Systems
2007 (English)In: International Workshops on Databases, Information Systems and Peer-to-Peer Computing, DBISP2P 2005/2006, 2007, 74-85 p.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 specification 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
2007. 74-85 p.
, Lecture Notes in Computer Science, ISSN 03029743 ; 4125
IdentifiersURN: urn:nbn:se:kth:diva-92105ScopusID: 2-s2.0-38149107532ISBN: 978-3-540-71660-0OAI: oai:DiVA.org:kth-92105DiVA: diva2:512043
International Workshops on Databases, Information Systems and Peer-to-Peer Computing, DBISP2P 2005/2006. Seoul. 11 September 2006 - 11 September 2006
QC 201203272012-03-262012-03-262012-03-27Bibliographically approved