Fault-tolerant routing in peer-to-peer systems

Simple item page
dc.creatorAspnes, James
dc.creatorDiamadi, Zoe
dc.creatorShah, Gauri
dc.date2003-02-15
dc.date2003-06-22
dc.date.accessioned2026-07-07T03:19:27Z
dc.date.available2026-07-07T03:19:27Z
dc.descriptionWe 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.
dc.descriptionFull version of PODC 2002 paper. New version corrects missing conditioning in Lemma 9 and some related details in the proof of Theorem 10, with no changes to main results
dc.identifierhttps://arxiv.org/abs/cs/0302022
dc.identifierhttp://arxiv.org/abs/cs/0302022
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31469
dc.subjectData Structures and Algorithms
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectF.2.2; C.2.4; E.1
dc.titleFault-tolerant routing in peer-to-peer systems
dc.typetext

Files

Collections

arXiv