A distributed polylogarithmic time algorithm for self-stabilizing skip graphs

ABSTRACT

Peer-to-peer systems rely on scalable overlay networks that enable efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to static communication networks, peer-to-peer networks allow nodes to adapt their neighbor set over time in order to react to join and leave events and failures. This paper shows how to maintain such networks in a robust manner. Concretely, we present a distributed and self-stabilizing algorithm that constructs a (variant of the) skip graph in polylogarithmic time from any initial state in which the overlay network is still weakly connected. This is an exponential improvement compared to previously known self-stabilizing algorithms for overlay networks. In addition, individual joins and leaves are handled locally and require little work.

REFERENCES

• 1: Yehuda Afek , Shlomi Dolev, Local stabilizer, Journal of Parallel and Distributed Computing, v.62 n.5, p.745-765, May 2002 [doi>10.1006/jpdc.2001.1823]
• 2: Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu , Yitong Yin, Fast construction of overlay networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073991]
• 3: James Aspnes , Gauri Shah, Skip graphs, ACM Transactions on Algorithms (TALG), v.3 n.4, p.37-es, November 2007 [doi>10.1145/1290672.1290674]
• 4: James Aspnes , Udi Wieder, The expansion and mixing time of skip graphs with applications, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073989]
• 5: J. Aspnes and Y. Wu. O(log n)-time overlay network construction from graphs with out-degree 1. In Proc. International Conference on Principles of Distributed Systems (OPODIS), volume 4878 of LNCS, pages 286--300, 2007.
• 6: Baruch Awerbuch , Boaz Patt-Shamir , George Varghese, Self-stabilization by local checking and correction (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.268-277, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185378]
• 7: Baruch Awerbuch , Christian Scheideler, Peer-to-peer systems for prefix search, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.123-132, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872053]
• 8: Baruch Awerbuch , Christian Scheideler, The hyperring: a low-congestion deterministic data structure for distributed environments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 9: Baruch Awerbuch , George Varghese, Distributed program checking: a paradigm for building self-stabilizing distributed protocols (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.258-267, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185377]
• 10: Ankur Bhargava , Kishore Kothapalli , Chris Riley , Christian Scheideler , Mark Thober, Pagoda: a dynamic overlay network for routing, data management, and multicasting, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007938]
• 11: J. Brzezinski and M. Szychowiak. Self-stabilization in distributed systems--a short survey. Foundations of Computing and Decision Sciences, 25(1), 2000.
• 12: Thomas Clouser , Mikhail Nesterenko , Christian Scheideler, Tiara: A Self-stabilizing Deterministic Skip List, Proceedings of the 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems, November 21-23, 2008, Detroit, MI [doi>10.1007/978-3-540-89335-6_12]
• 13: Adam M. Costello , George Varghese, Self-stabilization by window washing, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.35-44, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248056]
• 14: C. Cramer and T. Fuhrmann. Self-stabilizing ring networks on connected graphs. Technical Report 2005-5, System Architecture Group, University of Karlsruhe, 2005.
• 15: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 16: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 17: S. Dolev and T. Herman. Superstabilizing protocols for dynamic distributed systems. Chicago Journal of Theoretical Computer Science, 4:1--40, 1997.
• 18: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 19: D. Gall, R. Jacob, A. Richa, C. Scheideler, S. Schmid, and H. Täubig. Modeling scalability in distributed self-stabilization: The case of graph linearization. Technical Report TUM-I0835, Technische Universität München, Computer Science Dept., Nov. 2008.
• 20: Michael T. Goodrich , Michael J. Nelson , Jonathan Z. Sun, The rainbow skip graph: a fault-tolerant constant-degree distributed data structure, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.384-393, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109601]
• 21: Nicholas J. A. Harvey , J. Ian Munro, Deterministic SkipNet, Information Processing Letters, v.90 n.4, p.205-208, 31 May 2004 [doi>10.1016/j.ipl.2004.01.019]
• 22: Nicholas J. A. Harvey , Michael B. Jones , Stefan Saroiu , Marvin Theimer , Alec Wolman, SkipNet: a scalable overlay network with practical locality properties, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.9-9, March 26-28, 2003, Seattle, WA
• 23: T. Herman. Observations on time adaptive self-stabilization. Technical Report TR 97-07, University of Iowa, 1997.
• 24: T. Herman. Self-stabilization bibliography: Access guide. University of Iowa, December 2002. See ftp://ftp.cs.uiowa.edu/pub/selfstab/bibliography/.
• 25: Shmuel Katz , Kenneth J. Perry, Self-stabilizing extensions for message-passing systems, Distributed Computing, v.7 n.1, p.17-26, November 1993 [doi>10.1007/BF02278852]
• 26: Shay Kutten , Boaz Patt-Shamir, Time-adaptive self stabilization, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.149-158, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259435]
• 27: Shay Kutten , David Peleg, Fault-local distributed mending (extended abstract), Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.20-27, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224967]
• 28: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 29: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 30: Moni Naor , Udi Wieder, Novel architectures for P2P applications: The continuous-discrete approach, ACM Transactions on Algorithms (TALG), v.3 n.3, p.34-es, August 2007 [doi>10.1145/1273340.1273350]
• 31: M. Onus, A. Richa, and C. Scheideler. Linearization: Locally self-stabilizing sorting in graphs. In Proc. 9th ALENEX, 2007.
• 32: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 33: Ayman Shaker , Douglas S. Reeves, Self-Stabilizing Structured Ring Topology P2P Systems, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.39-46, August 31-September 02, 2005 [doi>10.1109/P2P.2005.34]
• 34: I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. Technical Report MIT-LCS-TR-819, MIT, 2001.
• 35: George Varghese, Self-stabilization by local checking and correction, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 36: George Varghese, Self-stabilization by counter flushing, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.244-253, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198102]

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
peer-to-peer systems