The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure
| dc.creator | Goodrich, Michael T. | |
| dc.creator | Nelson, Michael J. | |
| dc.creator | Sun, Jonathan Z. | |
| dc.date | 2009-05-13 | |
| dc.date.accessioned | 2026-07-07T13:14:55Z | |
| dc.date.available | 2026-07-07T13:14:55Z | |
| dc.description | 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. | |
| dc.description | Expanded version of a paper appearing in ACM-SIAM Symp. on Discrete Algorithms (SODA) | |
| dc.identifier | https://arxiv.org/abs/0905.2214 | |
| dc.identifier | http://arxiv.org/abs/0905.2214 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/230329 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Networking and Internet Architecture | |
| dc.title | The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure | |
| dc.type | text |