Academic
Publications
Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks

Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks,10.1007/978-3-540-39989-6_23,Kirsten Hildrum,John Kubiatowicz

Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks   (Citations: 46)
BibTex | RIS | RefWorks Download
In this paper, we show that two peer-to-peer systems, Pas- try (13) and Tapestry (17) can be made tolerant to certain classes of failures and a limited class of attacks. These systems are said to oper- ate properly if they can nd the closest node matching a requested ID. The system must also be able to dynamically construct the necessary routing information when new nodes enter or the network changes. We show that with an additional factor of O(log n) storage overhead and O(log2 n) communication overhead, they can continue to achieve both of these goals in the presence of a constant fraction nodes that do not obey the protocol. Our techniques are similar in spirit to those of Saia et al. (14) and Naor and Wieder (10). Some simple simulations show that these techniques are useful even with constant overhead.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: