Skip graphs

ABSTRACT

Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes that may fail at any time. They are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. Unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. In addition, simple and straightforward algorithms can be used to construct a skip graph, insert new nodes into it, search it, and detect and repair errors within it introduced due to node failures.

REFERENCES

• 1: Abraham, I., Aspnes, J., and Yuan, J. 2005. Skip B-trees. In Proceedings of the 9th International Conference on Principles of Distributed Systems, 284--295.
• 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 , Zoë Diamadi , Gauri Shah, Fault-tolerant routing in peer-to-peer systems, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571862]
• 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: 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]
• 6: Y. Aumann , M. A. Bender, Fault tolerant data structures, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.580, October 14-16, 1996
• 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: Castro, M., Druschel, P., Hu, Y. C., and Rowstron, A. 2002. Topology-Aware routing in structured peer-to-peer overlay networks. In Proceedings of the International Workshop on Future Directions in Distributed Computing (FuDiCo), Bertinoro, Italy, A. Schiper, et al., eds. Lecture Notes in Computer Science, vol. 2584. Springer, 103--107.
• 9: Ian Clarke , Oskar Sandberg , Brandon Wiley , Theodore W. Hong, Freenet: a distributed anonymous information storage and retrieval system, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.46-66, January 2001, Berkeley, California, United States
• 10: Mayur Datar, Butterflies and Peer-to-Peer Networks, Proceedings of the 10th Annual European Symposium on Algorithms, p.310-322, September 17-21, 2002
• 11: de la Briandais, R. 1959. File searching using variable length keys. In Proceedings of the Western Joint Computer Conference, vol. 15, Montvale, NJ, 295--298.
• 12: Devroye, L. 1992. A limit theory for random skip lists. Ann. Appl. Probab. 2, 3, 597--609.
• 13: Amos Fiat , Jared Saia, Censorship resistant peer-to-peer content addressable networks, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.94-103, January 06-08, 2002, San Francisco, California
• 14: Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
• 15: Joaquim Gabarró , Conrado Martínez , Xavier Messeguer, A design of a parallel dictionary using skip lists, Theoretical Computer Science, v.158 n.1-2, p.1-33, May 20, 1996 [doi>10.1016/0304-3975(94)00288-6]
• 16: J. Gabarro , X. Messeguer, A unified approach to concurrent and parallel algorithms on balanced data structures, Proceedings of the 17th International Conference of the Chilean Computer Science Society (SCCC '97), p.78, November 12-14, 1997
• 17: Gnutella. 2007. Gnutella website. http://gnutella.wego.com.
• 18: Matthew Harren , Joseph M. Hellerstein , Ryan Huebsch , Boon Thau Loo , Scott Shenker , Ion Stoica, Complex Queries in DHT-based Peer-to-Peer Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.242-259, March 07-08, 2002
• 19: 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
• 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: Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564877]
• 22: Johnson, T., and Colbrook, A. 1994. A distributed, replicated, data-balanced search structure. Int. J. High Speed Comput. 6, 4 (Dec.), 475--500.
• 23: David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
• 24: Peter Kirschenhofer , Conrado Martínez , Helmut Prodinger, Analysis of an optimized search algorithm for skip lists, Theoretical Computer Science, v.144 n.1-2, p.199-220, June 26, 1995 [doi>10.1016/0304-3975(94)00296-U]
• 25: Peter Kirschenhofer , Helmut Prodinger, The path length of random skip lists, Acta Informatica, v.31 n.9, p.775-792, Nov. 1994
• 26: Knuth, D. E. 1973. The Art of Computer Programming: Sorting and Searching, vol. 3. Addison-Wesley, Reading, MA.
• 27: Li, X., Misra, J., and Plaxton, C. G. 2004. Active and concurrent topology maintenance. In Proceedings of the 18th International Conference on Distributed Computing (DISC), Amsterdam, The Netherlands, R. Guerraoui, ed. Lecture Notes in Computer Science, vol. 3274. Springer, 320--334.
• 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: Munro, J. I., and Poblete, P. V. 1984. Fault tolerance and storage reduction in binary search trees. Inf. Control 62, 2/3 (Aug.), 210--218.
• 30: Napster. 2003. Napster website. http://www.napster.com.
• 31: T. Papadakis , J. I. Munro , P. V. Poblete, Analysis of the expected search cost in skip lists, Proceedings of the second Scandinavian workshop on Algorithm theory, p.160-172, July 1990, Bergen, Sweden
• 32: Plaxton, C. G., Rajaraman, R., and Richa., A. W. 1999. Accessing nearby copies of replicated objects in a distributed environment. Theory Comput. Syst. 32, 3, 241--280.
• 33: 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]
• 34: 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
• 35: 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
• 36: Jared Saia , Amos Fiat , Steven D. Gribble , Anna R. Karlin , Stefan Saroiu, Dynamically Fault-Tolerant Content Addressable Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.270-279, March 07-08, 2002
• 37: Robert Sedgewick , Philippe Flajolet, An introduction to the analysis of algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 38: 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]
• 39: Silaghi, B., Bhattacharjee, B., and Keleher, P. 2002. Query Routing in the TerraDir distributed directory. In Proceedings of the SPIE ITCOM, vol. 4868, V. Firoiu and Z.-L. Zhang, eds. SPIE, Boston, 299--309.
• 40: Ion Stoica , Robert Morris , David Liben-Nowell , David R. Karger , M. Frans Kaashoek , Frank Dabek , Hari Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.17-32, February 2003 [doi>10.1109/TNET.2002.808407]
• 41: Zhang, Z., Shi, S., and Zhu, J. 2003. SOMO: Self-Organized metadata overlay for resource management in P2P DHT. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS), Berkeley, CA.
• 42: Zhao, B. Y., Joseph, A. D., and Kubiatowicz, J. D. 2002. Locality-Aware mechanisms for large-scale networks. In Proceedings of the Workshop on Future Directions in Distributed Computing (FuDiCo), Bertinoro, Italy, 80--83.
• 43: 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: Distributed data structures

Keywords:
Peer-to-peer, overlay networks, skip lists