Theory of Computing
-------------------
Title : Censorship Resistant Peer-to-Peer Networks
Authors : Amos Fiat and Jared Saia
Volume : 3
Number : 1
Pages : 1-23
URL : http://www.theoryofcomputing.org/articles/v003a001
Abstract
--------
We present a censorship resistant peer-to-peer network for
accessing n data items in a network of n nodes. Each
search for a data item in the network takes O(log n) time
and requires at most O(log^2 n) messages. Our network is
censorship resistant in the sense that even after adversarial
removal of an arbitrarily large constant fraction of the nodes
in the network, all but an arbitrarily small fraction of the
remaining nodes can obtain all but an arbitrarily small fraction
of the original data items. The network can be created in a fully
distributed fashion. It requires only O(log n) memory in each
node. We also give a variant of our scheme that has the property
that it is highly spam resistant: an adversary can take over complete
control of a constant fraction of the nodes in the network and yet
will still be unable to generate spam.