Fault-tolerant routing in peer-to-peer systems
<|reference_start|>Fault-tolerant routing in peer-to-peer systems: 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.<|reference_end|>
@article{aspnes2003fault-tolerant,
    title={Fault-tolerant routing in peer-to-peer systems},
    author={James Aspnes, Zoe Diamadi, and Gauri Shah},
    journal={arXiv preprint arXiv:cs/0302022},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0302022},
    primaryClass={cs.DS cs.DC}
}