## Fault-tolerant Routing in Peer-to-peer Systems

James Aspnes, Zoë Diamadi, Gauri Shah

Twenty-First ACM Symposium on Principles of Distributed Computing (PODC), July 2002, pp. 223-232.

Submitted toDistributed Computing.

Archived as arXiv:cs.DS/0302022.

## Abstract

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 heuristics to efficiently maintain a network supporting efficient routing as nodes enter and leave the system. Finally, we give some experimental results that suggest promising directions for future work.

- PODC 2002 proceedings version (PS) (PDF)
- PowerPoint Presentation

Bibtex:

@inproceedings{AspnesDS2002,

title="Fault-tolerant Routing in Peer-to-peer Systems",

author="James Aspnes and Zoe Diamadi and Gauri Shah",

booktitle="Twenty-First ACM Symposium on Principles of Distributed Computing",

pages="223--232",

month={21--24~} #jul,

year="2002",

address={Monterey, USA},

note="Submitted to {\em Distributed Computing}. Available at {\tt http://arXiv.org/abs/cs/0302022}.

}