Viceroy: A Scalable and Dynamic Emulation of the
Butterfly
Dahlia Malkhi Moni
Naor David Ratajczak
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, and 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 resources
and the presence or elimination of bottlenecks in the network.
Remark: Our network is called Viceroy after the
Viceroy butterfly
, which although identical in appearance to the
Monarch butterfly
is thought to be far more palatable (to birds). This is often given
as an example of evolutionary imitation (but see
here
for more recent views, based on D. Ritland and L. Brower [Nature 350:497-498
(1991)].
Postscript, gzipped Postscript, PDF
Related publications:
- Moni Naor and Udi Wieder, Novel Architectures for P2P Applications: the
Continuous-Discrete Approach, Proc. SPAA 2003,
Postscript,
gzipped Postscript, PDF.
- Moni Naor and Udi Wieder, A Simple Fault Tolerant Distributed Hash
Table, Proc. IPTPS 2003, Lecture Notes in Computer Science 2735,
Springer, pp. 88-97.
Postscript,
gzipped Postscript, PDF
- Moni
Naor and Udi
Wieder, Scalable and Dynamic Quorum Systems, Distributed Computing
17(4): 311-322 (2005),
Postscript,
gzipped Postscript, PDF
- Moni Naor and Udi Wieder,
Know thy Neighbor's Neighbor: Better Routing for Skip-Graphs and Small
Worlds, IPTPS 2004.
Postscript, gzipped Postscript,
PDF.
- G. S. Manku, M. Naor, U.
Wieder, Know thy Neighbor's Neighbor: The Power of Lookahead in
Randomized P2P Networks, STOC 2004, PDF.
Back to On-Line Publications
Recent publications
Back Home
