The rainbow skip graph: a fault-tolerant constant-degree distributed data structure

ABSTRACT

We present a distributed data structure, which we call the rainbow skip graph. To our knowledge, this is the first peer-to-peer data structure that simultaneously achieves high fault-tolerance, constant-sized nodes, and fast update and query times for ordered data. It is a non-trivial adaptation of the SkipNet/skip-graph structures of Harvey et al. and Aspnes and Shah, so as to provide fault-tolerance as these structures do, but to do so using constant-sized nodes, as in the family tree structure of Zatloukal and Harvey. It supports successor queries on a set of n items using O(log n) messages with high probability, an improvement over the expected O(log n) messages of the family tree. Our structure achieves these results by using the following new constructs:• Rainbow connections: parallel sets of pointers between related components of nodes, so as to achieve good connectivity between "adjacent" components, using constant-sized nodes.• Hydra components: highly-connected, highly fault-tolerant components of constant-sized nodes, which will contain relatively large connected subcomponents even under the failure of a constant fraction of the nodes in the component.We further augment the hydra components in the rainbow skip graph by using erasure-resilient codes to ensure that any large subcomponent of nodes in a hydra component is sufficient to reconstruct all the data stored in that component. By carefully maintaining the size of related components and hydra components to be O(log n), we are able to achieve fast times for updates and queries in the rainbow skip graph. In addition, we show how to make the communication complexity for updates and queries be worst case, at the expense of more conceptual complexity and a slight degradation in the node congestion of the data structure.

REFERENCES

• 1: N. Alon and M. Luby. A linear time erasure-resilient code with nearly optimal recovery. IEEE Transactions on Information Theory, 42, 1996.
• 2: Lars Arge , David Eppstein , Michael T. Goodrich, Skip-webs: efficient distributed data structures for multi-dimensional data sets, 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.1073827]
• 3: James Aspnes , Jonathan Kirsch , Arvind Krishnamurthy, Load balancing and locality in range-queriable data structures, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011785]
• 4: James Aspnes , Gauri Shah, Skip graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: 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]
• 6: R. Beigel , W. Hurwood , N. Kahale, Fault diagnosis in a flash, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.571, October 23-25, 1995
• 7: Richard Beigel , Grigorii Margulis , Daniel A. Spielman, Fault diagnosis in a small constant number of parallel testing rounds, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.21-29, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165234]
• 8: W. Du and M. T. G. and. Pipelining algorithms for cheater detection in computational grids. In ACM-SIAM Symp. on Discrete Algorithms (SODA), page under submission, 2006.
• 9: Prasanna Ganesan , Gurmeet Singh Manku, Optimal routing in Chord, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 10: Nicholas J. A. Harvey , J. Ian Munro, Brief announcement: deterministic skipnet, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.152-152, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872057]
• 11: N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman. SkipNet: A scalable overlay network with practical locality properties. In USENIX Symp. on Internet Technologies and Systems, Lecture Notes in Computer Science, 2003.
• 12: F. Kaashoek and D. R. Karger. Koorde: A simple degree-optimal distributed hash table. In 2nd Int. Workshop on Peer-to-Peer Systems, 2003.
• 13: G. S. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. In 4th USENIX Symp. on Internet Technologies and Systems, 2003.
• 14: Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007368]
• 15: M. Naor and U. Wieder. Know thy neighbor's neighbor: Better routing in skip-graphs and small worlds. In 3rd Int. Workshop on Peer-to-Peer Systems, 2004.
• 16: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 17: 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
• 18: Antony I. T. Rowstron , Anne-Marie Kermarrec , Miguel Castro , Peter Druschel, SCRIBE: The Design of a Large-Scale Event Notification Infrastructure, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.30-43, November 07-09, 2001
• 19: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 20: Kevin C. Zatloukal , Nicholas J. A. Harvey, Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 21: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Theory