Viceroy
Top Cited Papers
- 21 July 2002
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 183-192
- https://doi.org/10.1145/571825.571857
Abstract
We propose a family of constant-degree routing networks of logarithmic diameter, with the additional property that the addition or removal of a node to the network requires no global coordination, only a constant number of linkage changes in expectation, and a logarithmic number with high probability. Our randomized construction improves upon existing solutions, such as balanced search trees, by ensuring that the congestion of the network is always within a logarithmic factor of the optimum with high probability. Our construction derives from recent advances in the study of peer-to-peer lookup networks, where rapid changes require efficient and distributed maintenance, and where the lookup efficiency is impacted both by the lengths of paths to requested data and the presence or elimination of bottlenecks in the network.Keywords
This publication has 12 references indexed in Scilit:
- A scalable content-addressable networkPublished by Association for Computing Machinery (ACM) ,2001
- ChordPublished by Association for Computing Machinery (ACM) ,2001
- Linear hash functionsJournal of the ACM, 1999
- Consistent hashing and random treesPublished by Association for Computing Machinery (ACM) ,1997
- Accessing nearby copies of replicated objects in a distributed environmentPublished by Association for Computing Machinery (ACM) ,1997
- LH*—a scalable, distributed data structureACM Transactions on Database Systems, 1996
- Clocked adversaries for hashingAlgorithmica, 1993
- UPDATING BINARY TREES WITH CONSTANT LINKAGE COSTInternational Journal of Foundations of Computer Science, 1992
- Skip lists: a probabilistic alternative to balanced treesCommunications of the ACM, 1990
- Interconnection Networks for SIMD MachinesComputer, 1979