Low Stretch between Nearby Peers

Kirsten Hildrum, John D. Kubiatowicz and Jeremy Stribling

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1328
June 2004

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1328.pdf

A decentralized object location and routing data structure (or DOLR) locates copies of objects in peer-to-peer networks. An efficient DOLR finds nearby copies of objects when possible. The measure of efficiency is stretch, the ratio of the distance traveled to find an object to the distance to the closest copy. Previous empirical work has shown that achieving low stretch is more difficult when the objects are nearby, and here we give one reason why that is the case.

Second, one of the primitives used for building a DOLR is finding a nearby peer in the peer-to-peer network. We compare two techniques for finding the nearest neighbor in a peer-to-peer network.


BibTeX citation:

@techreport{Hildrum:CSD-04-1328,
    Author = {Hildrum, Kirsten and Kubiatowicz, John D. and Stribling, Jeremy},
    Title = {Low Stretch between Nearby Peers},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2004},
    Month = {Jun},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5532.html},
    Number = {UCB/CSD-04-1328},
    Abstract = {A decentralized object location and routing data structure (or DOLR) locates copies of objects in peer-to-peer networks. An efficient DOLR finds nearby copies of objects when possible. The measure of efficiency is stretch, the ratio of the distance traveled to find an object to the distance to the closest copy. Previous empirical work has shown that achieving low stretch is more difficult when the objects are nearby, and here we give one reason why that is the case. <p> Second, one of the primitives used for building a DOLR is finding a nearby peer in the peer-to-peer network. We compare two techniques for finding the nearest neighbor in a peer-to-peer network.}
}

EndNote citation:

%0 Report
%A Hildrum, Kirsten
%A Kubiatowicz, John D.
%A Stribling, Jeremy
%T Low Stretch between Nearby Peers
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1328
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5532.html
%F Hildrum:CSD-04-1328