The hyperring: a low-congestion deterministic data structure for distributed environments

ABSTRACT

In this paper we study the problem of designing searchable concurrent data structures with performance guarantees that can be used in a distributed environment where data elements are stored in a dynamically changing set of nodes. Searchable data structures are data structures that provide three basic operations: INSERT, DELETE, and SEARCH. In addition to searching for an exact match, we demand that for a data structure to be called "searchable", Search also has to be able to search for the closest successor or predecessor of a data item. Such a property has a tremendous advantage over just exact match, because it would allow to implement many data base applications.We are interested in finding a searchable concurrent data structure that has (1) a low degree, (2) requires a small amount of work for INSERT and DELETE operations, and (3) is able to handle concurrent search requests with low congestion and dilation.We present the first deterministic concurrent data structure, called Hyperring, that can fulfill all of these objectives in a polylogarithmic way. In fact, the Hyperring has a degree of O(log n), requires O(log³ n) work for INSERT and DELETE operations, and can handle concurrent search requests to random destinations, one request per node, with congestion and dilation O(log n) w.h.p.Most of the previous solutions for distributed environments are not searchable (in our sense) but only provide exact lookup, and those that are searchable do not have proofs about the congestion caused by concurrent search requests.

REFERENCES

• 1: James Aspnes , Gauri Shah, Skip graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 2: 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
• 3: B. Awerbuch and C. Scheideler. The Hyperring: A low-congestion deterministic data structure for distributed environments. Technical report, Johns Hopkins University, 2003. See http://www.cs.jhu.edu~scheideler.
• 4: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.295-304, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301323]
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: 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]
• 7: Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
• 8: N. J. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman. Skipnet: A scalable overlay network with practical locality properties. In USITS 2003.
• 9: 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]
• 10: P. Krishna. Highly Scalable Data Balanced Distributed Search Structures. Ph.D. thesis, University of Florida, 1995.
• 11: Xiaozhou Li , C. Greg Plaxton, On name resolution in peer-to-peer networks, Proceedings of the second ACM international workshop on Principles of mobile computing, October 30-31, 2002, Toulouse, France [doi>10.1145/584490.584507]
• 12: 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]
• 13: X. Messeguer. Skip trees, an alternative data structure to skip lists in a concurrent approach. Informatique Theorique et Applications 31(3):251--269, 1997.
• 14: J. Ian Munro , Thomas Papadakis , Robert Sedgewick, Deterministic skip lists, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.367-375, September 1992, Orlando, Florida, United States
• 15: Moni Naor , Udi Wieder, Novel architectures for P2P applications: the continuous-discrete approach, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777421]
• 16: W. Paul, U. Vishkin, and H. Wagener. Parallel computation on 2--3 trees. RAIRO -- Theoretical Informatics 17(4):397--404, 1983.
• 17: William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Proceedings of the Workshop on Algorithms and Data Structures, p.437-449, August 17-19, 1989
• 18: 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
• 19: 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
• 20: Christian Scheideler , J. Van Leeuwen , J. Hartmanis , G. Goos, Universal Routing Strategies for Interconnection Networks, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 21: Dennis Shasha , Nathan Goodman, Concurrent search structure algorithms, ACM Transactions on Database Systems (TODS), v.13 n.1, p.53-90, March 1988 [doi>10.1145/42201.42204]
• 22: 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
• 23: 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