The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure

Details The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure

2009-05-13

arxiv.org/abs/0905.2214v1

Computer Science

Data Structures and Algorithms

Expanded version of a paper appearing in ACM-SIAM Symp. on Discrete Algorithms (SODA)

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-399623