Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks
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.