Farsite: federated, available, and reliable storage for an incompletely trusted environment

Abstract

Farsite is a secure, scalable file system that logically functions as a centralized file server but is physically distributed among a set of untrusted computers. Farsite provides file availability and reliability through randomized replicated storage; it ensures the secrecy of file contents with cryptographic techniques; it maintains the integrity of file and directory data with a Byzantine-fault-tolerant protocol; it is designed to be scalable by using a distributed hint mechanism and delegation certificates for pathname translations; and it achieves good performance by locally caching file data, lazily propagating file updates, and varying the duration and granularity of content leases. We report on the design of Farsite and the lessons we have learned by implementing much of that design.

References

1. T. Anderson, M. Dahlin, J. Neefe, D. Patterson, D. Roselli, R. Wang. Serverless Network File Systems. 15th SOSP, Dec 1995.]]
2. R. J. Anderson, "The Eternity Service", PRAGO-CRYPT '96, CTU Publishing, Sep/Oct 1996.]]
3. R. E. Blahut, Theory and Practice of Error Control Codes, Addison Wesley, 1983.]]
4. M. G. Baker, J. H. Hartman, M. D. Kupfer, K. W. Shirriff, J. K. Ousterhout. "Measurements of a Distributed File System." 13th SOSP, Oct 1991.]]
5. M. Blaze, "A Cryptographic File System for Unix", 1st Computer and Comm. Security, ACM, Nov 1993.]]
6. W. J. Bolosky, J. R. Douceur, D. Ely, and M. Theimer, "Feasibility of a Serverless Distributed File System Deployed on an Existing Set of Desktop PCs", SiGMETRICS 2000, ACM, Jun 2000.]]
7. W. J. Bolosky, S. Corbin, D. Goebel, J. R. Douceur. Single Instance Storage in Windows 2000. 4th Usenix Windows System Symposium, Aug 2000.]]
8. M. Castro and B. Liskov, "Practical Byzantine Fault Tolerance", 3rd OSDI, USENIX, Feb 1999.]]
9. I. Clarke, O. Sandberg, B. Wiley, and T. Hong, "Freenet: A Distributed Anonymous Information Storage and Retrieval System", ICSI Workshop on Design Issues in Anonymity and Unobervability, Jul 2000.]]
10. F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica, "Wide-Area Cooperative Storage with CFS", SOSP, Oct 2001.]]
11. J. R. Douceur, "The Sybil Attack", 1st IPTPS, Mar 2002.]]
12. J. R. Douceur, A. Adya, W. J. Bolosky, D. Simon, M. Theimer, "Reclaiming Space from duplicate Files in a Serverless Distributed File System", ICDCS, Jul 2002.]]
13. J. R. Douceur and W. J. Bolosky, "A Large-Scale Study of File-System Contents", SIGMETRICS, May 1999.]]
14. J. R. Douceur and R. P. Wattenhofer, "Optimizing File Availability in a Secure Serverless Distributed File System", 20th SRDS, IEEE, Oct 2001.]]
15. J. R. Douceur, A. Adya; J. Benaloh; W. J. Bolosky; G. Yuval, "A Secure Directory Service based on Exclusive Encryption", (to appear) 18th ACSAC, Dec 2002.]]
16. J. Gemmell, E. M. Schooler, J. Gray, "Fcast Multicast File Distribution: 'Tune in, Download, and Drop Out'", Internet, Multimedia Systems and Applications, 1999.]]
17. Gnutella, http://gnutelladev.wego.com.]]
18. A. Goldberg and P. Yianilos, "Towards an Archival Intermemory", International Forum on Research and Technology Advances in Digital Libraries, Apr 1998.]]
19. J. Gray. "Why do Computers Stop and What Can Be Done About It?", 5th SRDS, Jan. 1986.]]
20. J. Gray and A. Reuter, Transaction Processiong: Concepts and Techniques. Morgan Kaufmann, 1993.]]
21. J. Howard, M. Kazar, S. Menees, D. Nichols, M. Satyanarayanan, R. Sidebotham, M. West, "Scale and Performance in a Distributed File System", TOCS 6(1), Feb 1988.]]
22. J. Kistler, M. Satyanarayanan. Disconnected operation in the Coda File System. TOCS 10(l), Feb 1992.]]
23. J. Kubiatowicz, et al., "OceanStore: An Architecture for Global-Scale Persistent Storage", 9th ASPLOS, ACM, Nov 2000.]]
24. E. Lee, C. Thekkath. Petal: Distributed virtual disks. 7th ASPLOS, Oct 1996.]]
25. M. Luby, "Benchmark Comparisons of Erasure Codes", http://www.icsi.berkeley.edu/~luby/erasure.html]]
26. D. Mazières, M. Kaminsky, M. F. Kaashoek, E. Witchel, "Separating Key Management from File System Security", SOSP, Dec 1999.]]
27. D. Mazières and D. Shasha, "Don't Trust Your File Server", 8th HotOS, May 2001.]]
28. M. McKusick, W. Joy, S. Leffler, R. Fabry. A Fast File System for UNIX. TOCS, 2(3):181--197, Aug 1984.]]
29. A. J. Menezes, P. C. van Oorschot, S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.]]
30. R. Merkle, "Protocols for Public Key Cryptosystems", IEEE Symposium on Security and Privacy, 1980.]]
31. Microsoft, "File Name Conventions", MSDN, Apt 2002.]]
32. Microsoft, "About Windows Update", http://v4.windowsupdate.microsoft.com/en/about.asp]]
33. Napster, http://www.napster.com.]]
34. E. Nemeth, G. Snyder, S. Seebass, T. R. Hein, UNIX System Administration Handbook, Prentice Hall, 2000.]]
35. J. K. Ousterhout, A, R. Cherenson, F. Douglis, M. N. Nelson, B. B. Welch, "The Sprite Network Operating System", IEEE Computer Group Magazine 21 (2), 1988.]]
36. M. Pease, R. Shostak, L. Lamport "Reaching Agreement in the Presence of Faults", JACM 27(2), Apr 1980.]]
37. G. J. Popek, R. G. Guy, T. W. Page, J. S. Heidemann, "Replication in Ficus Distributed File Systems", IEEE Workshop on Management of Replicated Data, 1990.]]
38. A. Rowstron and P. Druschel. "Storage Management and Caching in PAST, a Large-Scale, Persistent Peer-to-Peer Storage Utility", SOSP, Oct 2001.]]
39. R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, B. Lyon. Design and Implementation of the Sun Network File System. Summer USENIX Proceedings, 1985.]]
40. D. S. Santry, M. J. Feeley, N. C. Hutchinson, A. C. Veitch, R. W. Carton, J. Ofir, "Deciding When to Forget in the Elephant File System", 17th SOSP, Dec 1999.]]
41. S. T. Shafer, "The Enemy Within", Red Herring, Jan 2002.]]
42. D. A. Solomon and M. E. Russinovich, Inside Microsoft Windows 2000 Third Edition, Microsoft Press, 2000.]]
43. A. Sweeny, D. Doucette, W. Hu, C. Anderson, M. Nishimoto, G. Peck, "Scalability in the XFS File System", USENIX, 1996.]]
44. D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System, 15th SOSP, 1995.]]
45. C. Thekkath, T. Mann, E. Lee. Frangipani: A Scalable Distributed File System. 16th SOSP, Dec 1997.]]
46. M. Tompa and H. Woll, "How to Share a Secret with Cheaters", Journal of Cryptology 1(2), 1998.]]
47. S, Travaglia, P. Abrams, Bastard Operator from Hell, Plan Nine Publishing, Apr 2001.]]
48. W. Vogels. File system usage in Windows NT 4.0. 17th SOSP, Dec 1999.]]
49. J. Wylie, M. Bigrigg, J. Strunk, G. Ganger, H. Kilite, P. Khosla, "Survivalbe Information Storage Systems", IEEE Computer 33(8), Aug 2000.]]
50. B. Yee and J. D. Tygar, "Secure Coprocessors in Electronic Commerce Applications", USENIX 95, 1995.]]

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Reliability

• Security and privacy

  • Systems security

    • Operating systems security

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Distributed memory

    • Extra-functional properties

      • Software reliability

    • Software system structures

      • Distributed systems organizing principles