Maintaining replicas in unstructured P2P systems

ABSTRACT

Replication is widely used in unstructured peer-to-peer systems to improve search or achieve availability. We identify and solve a subclass of replication problems where each object is associated with a maintainer node, and its replicas should only be available as long as its maintainer is part of the network. Such requirement can be found in various applications, e.g., when objects are directory lists, service lists, or subscriptions of a publish/subscribe system.

We provide maintainers with proven guarantees on the number of replicas, in spite of network churn and crash failures. We also tackle the related problems of changing the number of replicas, updating replicas, balancing storage load in a heterogeneous network, and eliminating replicas left by crashing maintainers. Our algorithm is based on probabilistic methods and is simple to implement. We show by simulation and formal proof that our algorithm is correct.

REFERENCES

• 1: Reza Akbarinia , Esther Pacitti , Patrick Valduriez, Data currency in replicated DHTs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247506]
• 2: Asad Awan , Ronaldo A. Ferreira , Suresh Jagannathan , Ananth Grama, Distributed Uniform Sampling in Unstructured Peer-to-Peer Networks, Proceedings of the 39th Annual Hawaii International Conference on System Sciences, p.223.3, January 04-07, 2006 [doi>10.1109/HICSS.2006.126]
• 3: Ranjita Bhagwan , Kiran Tati , Yu-Chung Cheng , Stefan Savage , Geoffrey M. Voelker, Total recall: system support for automated availability management, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.25-25, March 29-31, 2004, San Francisco, California
• 4: P. Billingsley. Convergence of Probability Measures. Wiley-Interscience, second edition, July 1999.
• 5: Edith Cohen , Scott Shenker, Replication strategies in unstructured peer-to-peer networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 7: Anwitaman Datta , Manfred Hauswirth , Karl Aberer, Updates in Highly Unreliable, Replicated Peer-to-Peer Systems, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.76, May 19-22, 2003
• 8: Souptik Datta , Hillol Kargupta, Uniform Data Sampling from a Peer-to-Peer Network, Proceedings of the 27th International Conference on Distributed Computing Systems, p.50, June 25-27, 2007
• 9: Ronaldo A. Ferreira , Murali Krishna Ramanathan , Asad Awan , Ananth Grama , Suresh Jagannathan, Search with Probabilistic Guarantees in Unstructured Peer-to-Peer Networks, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.165-172, August 31-September 02, 2005 [doi>10.1109/P2P.2005.33]
• 10: Ronaldo A. Ferreira , Murali K. Ramanathan , Ananth Grama , Suresh Jagannathan, Randomized Protocols for Duplicate Elimination in Peer-to-Peer Storage Systems, IEEE Transactions on Parallel and Distributed Systems, v.18 n.5, p.686-696, May 2007 [doi>10.1109/TPDS.2007.351710]
• 11: Vijay Gopalakrishnan , Bujor Silaghi , Bobby Bhattacharjee , Pete Keleher, Adaptive Replication in Peer-to-Peer Systems, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.360-369, March 24-26, 2004
• 12: J. Kangasharju, K. W. Ross, and D. A. Turner. Optimizing File Availability in Peer-to-Peer Content Distribution. In INFOCOM, 2007.
• 13: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 14: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 15: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 16: Laurent Massoulié , Erwan Le Merrer , Anne-Marie Kermarrec , Ayalvadi Ganesh, Peer counting and sampling in overlay networks: random walk methods, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146402]
• 17: Ruggero Morselli , Bobby Bhattacharjee , Aravind Srinivasan , Michael A. Marsh, Efficient lookup on unstructured topologies, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073828]
• 18: Damon Mosk-Aoyama , Devavrat Shah, Computing separable functions via gossip, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146401]
• 19: S. Saroiu, P. K. Gummadi, and S. D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. In Multimedia Comp. and Networking, 2002.
• 20: Nima Sarshar , P. Oscar Boykin , Vwani P. Roychowdhury, Percolation Search in Power Law Networks: Making Unstructured Peer-to-Peer Networks Scalable, Proceedings of the Fourth International Conference on Peer-to-Peer Computing, p.2-9, August 25-27, 2004 [doi>10.1109/P2P.2004.39]
• 21: E. Sit, A. Haeberlen, F. Dabek, B. Chun, H. Weatherspoon, R. Morris, M. F. Kaashoek, and J. Kubiatowicz. Proactive Replication for Data Durability. In IPTPS, 2006.
• 22: Moritz Steiner , Taoufik En-Najjary , Ernst W. Biersack, A global view of kad, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298323]
• 23: Wesley W. Terpstra , Jussi Kangasharju , Christof Leng , Alejandro P. Buchmann, Bubblestorm: resilient, probabilistic, and exhaustive peer-to-peer search, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Design, Experimentation, Measurement, Performance