Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present a censorship resistant peer-to-peer Content Addressable 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²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.

REFERENCES

• 1: Noga Alon , Haim Kaplan , Michael Krivelevich , Dahlia Malkhi , Julien P. Stern, Scalable Secure Storage when Half the System Is Faulty, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.576-587, July 09-15, 2000
• 2: Noga Alon and Joel Spencer. The Probabilistic Method, 2nd Edition. John Wiley & Sons, 2000.
• 3: Y. Aumann , M. A. Bender, Fault tolerant data structures, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.580, October 14-16, 1996
• 4: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 5: John Borland. Gnutella girds against spam attacks. CNET News.com, August 2000. http://news.cnet.com/news/0-1005-200-2489605.html.
• 6: Clip2. Gnutella: To the bandwidth barrier and beyond. http://dss.clip2.com/gnutella.html.
• 7: Electronic Freedom Foundation. Eff --- censorship --- internet censorship legislation & regulation (cda, etc.) --- archive. http://www.eff.org/-pub/Censorship/Internet_censorship_bills.
• 8: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 9: J. Hastad , T. Leighton, Fast computation using faulty hypercubes, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.251-263, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73031]
• 10: Anna R. Karlin , Greg Nelson , Hisao Tamaki, On the fault tolerance of the butterfly, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.125-133, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195117]
• 11: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 12: F. Thomson Leighton , Bruce M. Maggs , Ramesh K. Sitaraman, On the Fault Tolerance of Some Popular Bounded-Degree Networks, SIAM Journal on Computing, v.27 n.5, p.1303-1333, Oct. 1998 [doi>10.1137/S0097539793255163]
• 13: Dahlia Malkhi , Michael K. Reiter , Avishai Wool, The Load and Availability of Byzantine Quorum Systems, SIAM Journal on Computing, v.29 n.6, p.1889-1906, April 2000 [doi>10.1137/S0097539797325235]
• 14: Dahlia Malkhi , Michael Reiter , Avishai Wool , Rebecca N. Wright, Probabilistic Byzantine quorum systems, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.321, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277781]
• 15: Aviel D. Rubin Marc Waldman and Lorrie Faith Cranor. Publius: A robust, tamper-evident, censorship-resistant, web publishing system. In Proc. 9th USENIX Security Symposium, pages 59-72, August 2000.
• 16: Robert Marquand. China's web users kept on their toes. http://www.csmonitor.com/durable/-2000/12/07/fp7s1-csm.shtml.
• 17: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 18: Index on Censorship. Index on censorship homepage. http://www.indexoncensorship.org.
• 19: Andrew Oram , Andy Oram, Peer-to-Peer: Harnessing the Power of Disruptive Technologies, O'Reilly & Associates, Inc., Sebastopol, CA, 2001
• 20: Gopal Pandurangan, Prabhakar Raghavan, and Eli Upfal. Building low-diameter p2p networks. In STOC 2001, Crete, Greece, 2001.
• 21: M. Pinsker. On the complexity of a concentrator. In 7th International Teletraffic Conference, 1973.
• 22: C. Greg Plaxton , Rajmohan Rajaraman , Andréa W. Richa, Accessing nearby copies of replicated objects in a distributed environment, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.311-320, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258523]
• 23: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 24: Stefan Saroiu, P. Krishna Gummadi, and Steven D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. In Proceedings of Multimedia Computing and Networking, 2002.
• 25: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 26: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 27: Gnutella website. http://gnutella.wego.com/.
• 28: Napster website. http://www.napster.com/.
• 29: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001