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

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-02-1178
April 2002

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2002/CSD-02-1178.pdf

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},
    Institution = {EECS Department, University of California, Berkeley},
    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