2009/05/13 by Michael T. Goodrich, Goodrich, Michael T., Michael J. Nelson +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #cs.DS #cs.NI
paper · pdf · doi:10.48550/arxiv.0905.2214
Expanded version of a paper appearing in ACM-SIAM Symp. on Discrete Algorithms (SODA)
arxiv created 2009/05/13 · arxiv updated 2009/12/01
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.