Preserving peer replicas by rate-limited sampled voting

ABSTRACT

The LOCKSS project has developed and deployed in a world-wide test a peer-to-peer system for preserving access to journals and other archival information published on the Web. It consists of a large number of independent, low-cost, persistent web caches that cooperate to detect and repair damage to their content by voting in "opinion polls." Based on this experience, we present a design for and simulations of a novel protocol for voting in systems of this kind. It incorporates rate limitation and intrusion detection to ensure that even some very powerful adversaries attacking over many years have only a small probability of causing irrecoverable damage before being detected.

REFERENCES

• 1: M. Abadi, M. Burrows, M. Manasse, and T. Wobber. Moderately Hard, Memory-bound Functions. In 10th Annual Network and Distributed System Security Symp., San Diego, CA, USA, February 2003.
• 2: R. J. Anderson. The Eternity Service. In 1st Intl. Conf. on the Theory and Applications of Cryptology, Prague, Czech Republic, 1996.
• 3: Assoc. of Research Libraries. ARL Statistics 2000-01. http://www.arl.org/stats/arlstat/01pub/intro.html, 2001.
• 4: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 5: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 6: Yuan Chen , Jan Edler , Andrew Goldberg , Allan Gottlieb , Sumeet Sobti , Peter Yianilos, A prototype implementation of archival Intermemory, Proceedings of the fourth ACM conference on Digital libraries, p.28-37, August 11-14, 1999, Berkeley, California, United States [doi>10.1145/313238.313249]
• 7: B. Chor and C. Dwork. Randomization in Byzantine Agreement. Advances in Computing Research, 5:443--497, 1989.
• 8: Ian Clarke , Oskar Sandberg , Brandon Wiley , Theodore W. Hong, Freenet: a distributed anonymous information storage and retrieval system, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.46-66, January 2001, Berkeley, California, United States
• 9: ConservationOnline. Electronic Storage Media. http://palimpsest.stanford.edu/bytopic/electronic-records/electronic-storage-media/, 2003.
• 10: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 11: D. Davis. Compliance Defects in Public-Key Cryptography. In 6th USENIX Security Symp., pages 171--178, San Jose, CA, USA, July 1996.
• 12: W. Diffie. Perspective: Decrypting The Secret to Strong Security. http://news.com.com/2010-1071-980462.html, January 2003.
• 13: W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Trans. on Information Theory, IT-22(6):644--654, November 1976.
• 14: Roger Dingledine , Michael J. Freedman , David Molnar, The free haven project: distributed anonymous storage service, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.67-95, January 2001, Berkeley, California, United States
• 15: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 16: C. Dwork, A. Goldberg, and M. Naor. On Memory-Bound Functions for Fighting Spam. In 23rd Annual Intl. Cryptology Conference, Santa Barbara, CA, USA, August 2003. To appear.
• 17: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 18: Electronic Frontier Found. DMCA Archive. http://www.eff.org/IP/DMCA/.
• 19: M. Erdos and S. Cantor. Shibboleth Architecture DRAFT v05. http://shibboleth.internet2.edu/docs/draft-internet2-shibboleth-arch-v05.pdf, May 2002. Work in progress.
• 20: TJ Giuli and M. Baker. Narses: A Scalable, Flow-Based Network Simulator. Technical Report cs.PF/0211024, Computer Science Department, Stanford University, Stanford, CA, USA, November 2002.
• 21: M. Keller, V. Reich, and A. Herkovic. What is a Library Anymore, Anyway? First Monday, 8(5), May 2003. http://www.firstmonday.org/issues/issue8_5/keller/index.html.
• 22: 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
• 23: Dahlia Malkhi , Michael Reiter, Byzantine quorum systems, Distributed Computing, v.11 n.4, p.203-213, October 1998 [doi>10.1007/s004460050050]
• 24: Petros Maniatis , David S. H. Rosenthal , Mema Roussopoulos , Mary Baker , TJ Giuli , Yanto Muliadi, Preserving peer replicas by rate-limited sampled voting, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 25: N. Michalakis, D-M. Chiu, and D. S. H. Rosenthal. Long Term Data Resilience Using Opinion Polls. In 22nd IEEE Intl. Performance Computing and Communications Conference, Phoenix, AZ, USA, April 2003.
• 26: D. Mogge. Seven Years of Tracking Electronic Publishing: The ARL Directory of Electronic Journals, Newsletters and Academic Discussion Lists. Library Hi Tech, 17(1):17--25, 1999.
• 27: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 28: Michael K. Reiter, Secure agreement protocols: reliable and atomic group multicast in rampart, Proceedings of the 2nd ACM Conference on Computer and communications security, p.68-80, November 1994, Fairfax, Virginia, United States [doi>10.1145/191177.191194]
• 29: D. S. H. Rosenthal. A Digital Preservation Network Appliance Based on OpenBSD. In BSDcon, San Mateo, CA, USA, September 2003. To appear.
• 30: D. S. H. Rosenthal and V. Reich. Permanent Web Publishing. In USENIX Annual Technical Conf., Freenix Track, pages 129--140, San Diego, CA, USA, June 2000.
• 31: D. S. H. Rosenthal, M. Roussopoulos, P. Maniatis, and M. Baker. Economic Measures to Resist Attacks on a Peer-to-Peer Network. In Workshop on Economics of Peer-to-Peer Systems, Berkeley, CA, USA, June 2003.
• 32: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 33: Stuart Staniford , Vern Paxson , Nicholas Weaver, How to Own the Internet in Your Spare Time, Proceedings of the 11th USENIX Security Symposium, p.149-167, August 05-09, 2002
• 34: US Govt. Web Design and Usability Guidelines. http://usability.gov/guidelines/softhard.html.
• 35: W. Venema. Murphy's Law and Computer Security. In 6th USENIX Security Symp., San Jose, CA, USA, July 1996.
• 36: Marc Waldman , David Mazières, Tangler: a censorship-resistant publishing system based on document entanglements, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502002]
• 37: Matthew M. Williamson, Throttling Viruses: Restricting propagation to defeat malicious mobile code, Proceedings of the 18th Annual Computer Security Applications Conference, p.61, December 09-13, 2002
• 38: N. Wingfield. EBay's Figurine Scandal: Auction Site Merchant Disappears With The Goods. Wall Street J., Feb 22nd, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.7 Digital Libraries

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability

General Terms:
Design, Economics, Reliability

Keywords:
digital preservation, rate limiting, replicated storage