Kirsten Hildrum and John D. Kubiatowicz and Satish Rao and Ben Y. Zhao

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-02-1178

2002

Modern networking applications replicate data and services widely, leading to a need for location-independent routing -- the ability to route queries directly to objects using names that are independent of the objects' physical locations. Two important properties of a routing infrastructure are routing locality and rapid adaptation to arriving and departing nodes. We show how these two properties can be achieved with an efficient solution to the nearest-neighbor problem. We present a new distributed algorithm that can solve the nearest-neighbor problem for a restricted metric space. We describe our solution in the context of Tapestry, an overlay network infrastructure that employs techniques proposed by Plaxton, Rajaraman, and Richa.

---

BibTeX citation:

@techreport{Hildrum:CSD-02-1178,
    Author= {Hildrum, Kirsten and Kubiatowicz, John D. and Rao, Satish and Zhao, Ben Y.},
    Title= {Distributed Data Location in a Dynamic Network},
    Year= {2002},
    Month= {Apr},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2002/5214.html},
    Number= {UCB/CSD-02-1178},
    Abstract= {Modern networking applications replicate data and services widely, leading to a need for location-independent routing -- the ability to route queries directly to objects using names that are independent of the objects' physical locations. Two important properties of a routing infrastructure are routing locality and rapid adaptation to arriving and departing nodes. We show how these two properties can be achieved with an efficient solution to the nearest-neighbor problem. We present a new distributed algorithm that can solve the nearest-neighbor problem for a restricted metric space. We describe our solution in the context of Tapestry, an overlay network infrastructure that employs techniques proposed by Plaxton, Rajaraman, and Richa.},
}

EndNote citation:

%0 Report
%A Hildrum, Kirsten 
%A Kubiatowicz, John D. 
%A Rao, Satish 
%A Zhao, Ben Y. 
%T Distributed Data Location in a Dynamic Network
%I EECS Department, University of California, Berkeley
%D 2002
%@ UCB/CSD-02-1178
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2002/5214.html
%F Hildrum:CSD-02-1178