Samsara: honor among thieves in peer-to-peer storage

ABSTRACT

Peer-to-peer storage systems assume that their users consume resources in proportion to their contribution. Unfortunately, users are unlikely to do this without some enforcement mechanism. Prior solutions to this problem require centralized infrastructure, constraints on data placement, or ongoing administrative costs. All of these run counter to the design philosophy of peer-to-peer systems.Samsara enforces fairness in peer-to-peer storage systems without requiring trusted third parties, symmetric storage relationships, monetary payment, or certified identities. Each peer that requests storage of another must agree to hold a claim in return---a placeholder that accounts for available space. After an exchange, each partner checks the other to ensure faithfulness. Samsara punishes unresponsive nodes probabilistically. Because objects are replicated, nodes with transient failures are unlikely to suffer data loss, unlike those that are dishonest or chronically unavailable. Claim storage overhead can be reduced when necessary by forwarding among chains of nodes, and eliminated when cycles are created. Forwarding chains increase the risk of exposure to failure, but such risk is modest under reasonable assumptions of utilization and simultaneous, persistent failure.

REFERENCES

• 1: E. Adar and B. A. Huberman. Free riding on Gnutella. First Monday, 5(10), October 2000.
• 2: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 3: Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
• 4: Matt Blaze , John Ioannidis , Angelos D. Keromytis, Offline Micropayments without Trusted Hardware, Proceedings of the 5th International Conference on Financial Cryptography, p.21-40, February 19-22, 2002
• 5: William J. Bolosky , John R. Douceur , David Ely , Marvin Theimer, Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.34-43, June 18-21, 2000, Santa Clara, California, United States
• 6: Brian Cooper , Hector Garcia-Molina, Peer-to-Peer Resource Trading in a Reliable Distributed System, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.319-327, March 07-08, 2002
• 7: Landon P. Cox , Christopher D. Murray , Brian D. Noble, Pastiche: making backup cheap and easy, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060316]
• 8: 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
• 9: W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644--54, November 1976.
• 10: 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
• 11: John R. Douceur , William J. Bolosky, Progress-based regulation of low-importance processes, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.247-260, December 12-15, 1999, Charleston, South Carolina, United States
• 12: P. Ferguson and H. Berkowitz. Network renumbering overview: Why would i want it and what is it anyway? Internet RFC 2071, January 1997.
• 13: Yun Fu , Jeffrey Chase , Brent Chun , Stephen Schwab , Amin Vahdat, SHARP: an architecture for secure resource peering, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 14: Philippe Golle , Kevin Leyton-Brown , Ilya Mironov, Incentives for sharing in peer-to-peer networks, Proceedings of the 3rd ACM conference on Electronic Commerce, p.264-267, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501193]
• 15: G. Hardin. The tragedy of the commons. Science, 162:1243--1248, 1968.
• 16: J. Ioannidis, S. Ioannidis, A. D. Keromytis, and V. Prevelakis. Fileteller: Paying and getting paid for file storage. In Proceedings of the Sixth Annual Conference on Financial Cryptography, pages 282--299, Bermuda, March 2002.
• 17: A. Juels and J. Brainard. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In Proceedings of the Network and Distributed System Security Symposium, pages 151--165, San Diego, CA, February 1999.
• 18: M. Lillibridge, S. Elnikety, A. Birrell, M. Burrows, and M. Isard. A cooperative Internet backup scheme. In Proceedings of the USENIX Annual Technical Conference, pages 29--42, San Antonio, TX, June 2003.
• 19: S. Low, F. Paganini, J. Wang, S. Adlakha, and J. Doyle. Dynamics of TCP/RED and a scalable control. In Proceedings of IEEE/INFOCOM'02, New York, NY, June 2002.
• 20: Christopher R. Lumb , Jiri Schindler , Gregory R. Ganger, Freeblock Scheduling Outside of Disk Firmware, Proceedings of the Conference on File and Storage Technologies, p.275-288, January 28-30, 2002
• 21: T.-W. J. Ngan, D. S. Wallach, and P. Druschel. Enforcing fair sharing of peer-to-peer resources. In Proceedings of the Second International Workshop on Peer-to-Peer Systems, Berkeley, CA, February 2003.
• 22: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 23: 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
• 24: S. Saroiu, G. P. Krishna, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In Proceedings of the SPIE Conference on Multimedia Computing and Networking, pages 156--170, San Jose, CA, January 2002.
• 25: M. Satyanarayanan. RPC2 User Guide and Reference Manual. School of Computer Science, Carnegie Mellon University, October 1991.
• 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: T. Ylonen. SSH---Secure login connections over the Internet. In Proceedings of the 6th USENIX Security Symposium, pages 37--42, San Jose, CA, July 1996.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management

General Terms:
Management, Performance

Keywords:
distributed accounting, peer-to-peer storage systems