Distributed Data Location in a Dynamic Network
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
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}, 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