Abstract

We present the first peer-to-peer network which is provably robust to adversarial attack. Our network is robust in the sense that even after adversarial removal of half the nodes in the network, an arbitrarily large fraction of the remaining nodes can still access an arbitrarily large fraction of the original data items. We also give a variant of our scheme that has the property that it is highly spam resistant: an adversary can have complete control of a constant fraction of the peers and yet will still be unable to generate spam. Our network is fully distributed and has time and resource bounds which are competitive with other proposed peer-to-peer systems (e.g. Chord, CAN and Tapestry) which are not provably robust to adversarial attack.
This work appears in the Symposium on Discrete Algorithms, 2002, the Journal of Algorithms (by invitation), and the First International Workshop on Peer-to-peer Systems, 2002. The work is joint with Amos Fiat, Steve Gribble, Anna Karlin and Stefan Saroiu.