Computer Science – Data Structures and Algorithms
Scientific paper
2003-02-15
Computer Science
Data Structures and Algorithms
Full version of PODC 2002 paper. New version corrects missing conditioning in Lemma 9 and some related details in the proof of
Scientific paper
We consider the problem of designing an overlay network and routing mechanism that permits finding resources efficiently in a peer-to-peer system. We argue that many existing approaches to this problem can be modeled as the construction of a random graph embedded in a metric space whose points represent resource identifiers, where the probability of a connection between two nodes depends only on the distance between them in the metric space. We study the performance of a peer-to-peer system where nodes are embedded at grid points in a simple metric space: a one-dimensional real line. We prove upper and lower bounds on the message complexity of locating particular resources in such a system, under a variety of assumptions about failures of either nodes or the connections between them. Our lower bounds in particular show that the use of inverse power-law distributions in routing, as suggested by Kleinberg (1999), is close to optimal. We also give efficient heuristics to dynamically maintain such a system as new nodes arrive and old nodes depart. Finally, we give experimental results that suggest promising directions for future work.
Aspnes James
Diamadi Zoe
Shah Gauri
No associations
LandOfFree
Fault-tolerant routing in peer-to-peer systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fault-tolerant routing in peer-to-peer systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fault-tolerant routing in peer-to-peer systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-306865