Farsite

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	T. E. Anderson , M. D. Dahlin , J. M. Neefe , D. A. Patterson , D. S. Roselli , R. Y. Wang, Serverless network file systems, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.109-126, December 03-06, 1995, Copper Mountain, Colorado, United States
	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	Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
	5	Matt Blaze, A cryptographic file system for UNIX, Proceedings of the 1st ACM conference on Computer and communications security, p.9-16, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168590]
	6	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
	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	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
	9	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
	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	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
	12	John R. Douceur , Atul Adya , William J. Bolosky , Dan Simon , Marvin Theimer, Reclaiming Space from Duplicate Files in a Serverless Distributed File System, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.617, July 02-05, 2002
	13	John R. Douceur , William J. Bolosky, A large-scale study of file-system contents, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.59-70, May 01-04, 1999, Atlanta, Georgia, United States
	14	J. R. Douceur and R. P. Wattenhofer, "Optimizing File Availability in a Secure Serverless Distributed File System", 20th SRDS, IEEE, Oct 2001.
	15	John R. Douceur , Atul Adya , Josh Benaloh , William J. Bolosky , Gideon Yuval, A Secure Directory Service based on Exclusive Encryption, Proceedings of the 18th Annual Computer Security Applications Conference, p.172, December 09-13, 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. V. Goldberg , P. N. Yianilos, Towards an Archival Intermemory, Proceedings of the Advances in Digital Libraries Conference, p.147, April 22-24, 1998
	19	J. Gray. "Why do Computers Stop and What Can Be Done About It?", 5th SRDS, Jan. 1986.
	20	Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
	21	John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
	22	James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
	23	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
	24	Edward K. Lee , Chandramohan A. Thekkath, Petal: distributed virtual disks, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.84-92, October 01-04, 1996, Cambridge, Massachusetts, United States
	25	M. Luby, "Benchmark Comparisons of Erasure Codes", http://www.icsi.berkeley.edu/~luby/crasure.html
	26	David Mazières , Michael Kaminsky , M. Frans Kaashoek , Emmett Witchel, Separating key management from file system security, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.124-139, December 12-15, 1999, Charleston, South Carolina, United States
	27	David Mazieres, Don't Trust Your File Server, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.113, May 20-22, 2001
	28	Marshall K. McKusick , William N. Joy , Samuel J. Leffler , Robert S. Fabry, A fast file system for UNIX, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.181-197, Aug. 1984 [doi>10.1145/989.990]
	29	Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
	30	R. Merkle, "Protocols for Public Key Cryptosystems", IEEE Symposium on Security and Privacy, 1980.
	31	Microsoft, "File Name Conventions", MSDN, Apr 2002.
	32	Microsoft, "About Windows Update", http://v4.windowsupdate.microsoft.com/en/about.asp
	33	Napster, http://www.napster.com.
	34	Evi Nemeth , Garth Snyder , Scott Seebass , Trent R. Hein, UNIX system administration handbook (3rd ed.), Prentice Hall PTR, Upper Saddle River, NJ, 2000
	35	John K. Ousterhout , Andrew R. Cherenson , Frederick Douglis , Michael N. Nelson , Brent B. Welch, The Sprite Network Operating System, Computer, v.21 n.2, p.23-36, February 1988 [doi>10.1109/2.16]
	36	M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
	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	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
	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	Douglas S. Santry , Michael J. Feeley , Norman C. Hutchinson , Alistair C. Veitch , Ross W. Carton , Jacob Ofir, Deciding when to forget in the Elephant file system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.110-123, December 12-15, 1999, Charleston, South Carolina, United States
	41	S. T. Shafer, "The Enemy Within", Red Herring, Jan 2002.
	42	David A. Solomon , Mark Russinovich, Inside Microsoft Windows 2000, Microsoft Press, Redmond, WA, 2000
	43	A. Sweeny, D. Doucette, W. Hu, C. Anderson, M. Nishimoto, G. Peck, "Scalability in the XFS File System", USENLX, 1996.
	44	D. B. Terry , M. M. Theimer , Karin Petersen , A. J. Demers , M. J. Spreitzer , C. H. Hauser, Managing update conflicts in Bayou, a weakly connected replicated storage system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.172-182, December 03-06, 1995, Copper Mountain, Colorado, United States
	45	Chandramohan A. Thekkath , Timothy Mann , Edward K. Lee, Frangipani: a scalable distributed file system, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.224-237, October 05-08, 1997, Saint Malo, France
	46	M. Tompa , H. Woll, How to share a secret with cheaters, Journal of Cryptology, v.1 n.2, p.133-138, Aug. 1988
	47	S. Travaglia, P. Abrams, Bastard Operator from Hell, Plan Nine Publishing, Apr 2001.
	48	Werner Vogels, File system usage in Windows NT 4.0, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.93-109, December 12-15, 1999, Charleston, South Carolina, United States
	49	Jay J. Wylie , Michael W. Bigrigg , John D. Strunk , Gregory R. Ganger , Han Kiliççöte , Pradeep K. Khosla, Survivable Information Storage Systems, Computer, v.33 n.8, p.61-68, August 2000 [doi>10.1109/2.863969]
	50	B. Yee and J. D. Tygar, "Secure Coprocessors in Electronic Commerce Applications", USENIX 95, 1995.

Collaborative Colleagues:

Atul Adya: colleagues

William J. Bolosky: colleagues

Miguel Castro: colleagues

Gerald Cermak: colleagues

Ronnie Chaiken: colleagues

John R. Douceur: colleagues

Jon Howell: colleagues

Jacob R. Lorch: colleagues

Marvin Theimer: colleagues

Roger P. Wattenhofer: colleagues

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

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