Viceroy: A Scalable and Dynamic Emulation of the Butterfly

Dahlia Malkhi         Moni  Naor     David Ratajczak


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:


Back to On-Line Publications

Recent publications

Back Home