{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:29Z","timestamp":1750308749281,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0614784"],"award-info":[{"award-number":["CNS-0614784"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>Versioning file systems provide the ability to recover from a variety of failures, including file corruption, virus and worm infestations, and user mistakes. However, using versions to recover from data-corrupting events requires a human to determine precisely which files and versions to restore. We can create more meaningful versions and enhance the value of those versions by capturing the causal connections among files, facilitating selection and recovery of precisely the right versions after data corrupting events.<\/jats:p>\n          <jats:p>We determine when to create new versions of files automatically using the causal relationships among files. The literature on versioning file systems usually examines two extremes of possible version-creation algorithms: open-to-close versioning and versioning on every write. We evaluate causal versions of these two algorithms and introduce two additional causality-based algorithms: Cycle-Avoidance and Graph-Finesse.<\/jats:p>\n          <jats:p>We show that capturing and maintaining causal relationships imposes less than 7% overhead on a versioning system, providing benefit at low cost. We then show that Cycle-Avoidance provides more meaningful versions of files created during concurrent program execution, with overhead comparable to open\/close versioning. Graph-Finesse provides even greater control, frequently at comparable overhead, but sometimes at unacceptable overhead. Versioning on every write is an interesting extreme case, but is far too costly to be useful in practice.<\/jats:p>","DOI":"10.1145\/1629080.1629083","type":"journal-article","created":{"date-parts":[[2009,12,8]],"date-time":"2009-12-08T20:53:14Z","timestamp":1260305594000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Causality-based versioning"],"prefix":"10.1145","volume":"5","author":[{"given":"Kiran-Kumar","family":"Muniswamy-Reddy","sequence":"first","affiliation":[{"name":"Harvard School of Engineering and Applied Sciences, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David A.","family":"Holland","sequence":"additional","affiliation":[{"name":"Harvard School of Engineering and Applied Sciences, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,12,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(05)80360-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11890850_18"},{"volume-title":"Proceedings of the 16th International Conference on Very Large Databases.","author":"Cellary W.","key":"e_1_2_1_3_1","unstructured":"Cellary , W. and Jomier , G . 1990. Consistency of versions in objects-oriented databases . In Proceedings of the 16th International Conference on Very Large Databases. Cellary, W. and Jomier, G. 1990. Consistency of versions in objects-oriented databases. In Proceedings of the 16th International Conference on Very Large Databases."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376715"},{"volume-title":"Proceedings of the USENIX Technical Conference. 43--60","author":"Chutani S.","key":"e_1_2_1_5_1","unstructured":"Chutani , S. , Anderson , O. T. , Kazar , M. L. , Leverett , B. W. , Mason , W. A. , and Sidebotham , R. N . 1992. The Episode file system . In Proceedings of the USENIX Technical Conference. 43--60 . Chutani, S., Anderson, O. T., Kazar, M. L., Leverett, B. W., Mason, W. A., and Sidebotham, R. N. 1992. The Episode file system. In Proceedings of the USENIX Technical Conference. 43--60."},{"volume-title":"Proceedings of the USENIX Annual Technical Conference, FREENIX Track.","author":"Cornell B.","key":"e_1_2_1_6_1","unstructured":"Cornell , B. , Dinda , P. , and Bustamante , F . 2004. Wayback: A user-level versioning file system for Linux . In Proceedings of the USENIX Annual Technical Conference, FREENIX Track. Cornell, B., Dinda, P., and Bustamante, F. 2004. Wayback: A user-level versioning file system for Linux. In Proceedings of the USENIX Annual Technical Conference, FREENIX Track."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095826"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Ottawa Linux Symposium.","author":"Halcrow M. A.","year":"2005","unstructured":"Halcrow , M. A. 2005 . eCryptfs: An enterprise-class encrypted filesystem for Linux . Proceedings of the Ottawa Linux Symposium. Halcrow, M. A. 2005. eCryptfs: An enterprise-class encrypted filesystem for Linux. Proceedings of the Ottawa Linux Symposium."},{"volume-title":"Proceedings of the USENIX Winter Technical Conference. 235--245","author":"Hitz D.","key":"e_1_2_1_9_1","unstructured":"Hitz , D. , Lau , J. , and Malcolm , M . 1994. File system design for an nfs file server appliance . In Proceedings of the USENIX Winter Technical Conference. 235--245 . Hitz, D., Lau, J., and Malcolm, M. 1994. File system design for an nfs file server appliance. In Proceedings of the USENIX Winter Technical Conference. 235--245."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945467"},{"volume-title":"Proceedings of the 12th Annual Network and Distributed System Security Symposium.","author":"King S. T.","key":"e_1_2_1_11_1","unstructured":"King , S. T. , Mao , Z. M. , Lucchetti , D. G. , and Chen , P. M . 2005. Enriching intrusion alerts through multi-host causality . In Proceedings of the 12th Annual Network and Distributed System Security Symposium. King, S. T., Mao, Z. M., Lucchetti, D. G., and Chen, P. M. 2005. Enriching intrusion alerts through multi-host causality. In Proceedings of the 12th Annual Network and Distributed System Security Symposium."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/121132.121166"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC'07)","author":"Laadan O.","key":"e_1_2_1_13_1","unstructured":"Laadan , O. and Nieh , J . 2007. Transparent checkpoint-restart of multiple processes on commodity operating systems . In Proceedings of the USENIX Annual Technical Conference (ATC'07) . USENIX Association, Berkeley, CA, 1--14. Laadan, O. and Nieh, J. 2007. Transparent checkpoint-restart of multiple processes on commodity operating systems. In Proceedings of the USENIX Annual Technical Conference (ATC'07). USENIX Association, Berkeley, CA, 1--14."},{"volume-title":"Proceedings of the 3rd USENIX Conference on File and Storage Technologies (FAST'04)","author":"Muniswamy-Reddy K.","key":"e_1_2_1_14_1","unstructured":"Muniswamy-Reddy , K. , Wright , C. P. , Himmer , A. , and Zadok , E . 2004. A versatile and user-oriented versioning file system . In Proceedings of the 3rd USENIX Conference on File and Storage Technologies (FAST'04) . Muniswamy-Reddy, K., Wright, C. P., Himmer, A., and Zadok, E. 2004. A versatile and user-oriented versioning file system. In Proceedings of the 3rd USENIX Conference on File and Storage Technologies (FAST'04)."},{"volume-title":"Proceedings of the USENIX Annual Technical Conference.","author":"Muniswamy-Reddy K.-K.","key":"e_1_2_1_15_1","unstructured":"Muniswamy-Reddy , K.-K. , Braun , U. , Holland , D. A. , Macko , P. , Maclean , D. , Margo , D. , Seltzer , M. , and Smogor , R . 2009. Layering in provenance systems . In Proceedings of the USENIX Annual Technical Conference. Muniswamy-Reddy, K.-K., Braun, U., Holland, D. A., Macko, P., Maclean, D., Margo, D., Seltzer, M., and Smogor, R. 2009. Layering in provenance systems. In Proceedings of the USENIX Annual Technical Conference."},{"volume-title":"Proceedings of the USENIX Annual Technical Conference.","author":"Muniswamy-Reddy K.-K.","key":"e_1_2_1_16_1","unstructured":"Muniswamy-Reddy , K.-K. , Holland , D. A. , Braun , U. , and Seltzer , M . 2006. Provenance-aware storage systems . In Proceedings of the USENIX Annual Technical Conference. Muniswamy-Reddy, K.-K., Holland, D. A., Braun, U., and Seltzer, M. 2006. Provenance-aware storage systems. In Proceedings of the USENIX Annual Technical Conference."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1063786.1063789"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095830"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380211203"},{"volume-title":"Proceedings of the 1st USENIX Conference on File and Storage Technologies (FAST'02)","author":"Quinlan S.","key":"e_1_2_1_20_1","unstructured":"Quinlan , S. and Dorward , S . 2002. Venti: a new approach to archival storage . In Proceedings of the 1st USENIX Conference on File and Storage Technologies (FAST'02) . 89--101. Quinlan, S. and Dorward, S. 2002. Venti: a new approach to archival storage. In Proceedings of the 1st USENIX Conference on File and Storage Technologies (FAST'02). 89--101."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/319151.319159"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference.","author":"Shah S.","key":"e_1_2_1_22_1","unstructured":"Shah , S. , Soules , C. A. N. , Ganger , G. R. , and Noble , B. D . 2007. Using provenance to aid in personal file search . In Proceedings of the USENIX Annual Technical Conference. Shah, S., Soules, C. A. N., Ganger, G. R., and Noble, B. D. 2007. Using provenance to aid in personal file search. In Proceedings of the USENIX Annual Technical Conference."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376681"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference.","author":"Shrira L.","key":"e_1_2_1_24_1","unstructured":"Shrira , L. and Xu , H . 2006. Thresher: An efficient storage manager for copy-on-write snapshots . In Proceedings of the USENIX Annual Technical Conference. Shrira, L. and Xu, H. 2006. Thresher: An efficient storage manager for copy-on-write snapshots. In Proceedings of the USENIX Annual Technical Conference."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1084805.1084812"},{"volume-title":"Proceedings of the USENIX Security Symposium.","author":"Somayaji A.","key":"e_1_2_1_26_1","unstructured":"Somayaji , A. and Forrest , S . 2000. Automated response using system-call delays . In Proceedings of the USENIX Security Symposium. Somayaji, A. and Forrest, S. 2000. Automated response using system-call delays. In Proceedings of the USENIX Security Symposium."},{"volume-title":"Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST'03)","author":"Soules C. A. N.","key":"e_1_2_1_27_1","unstructured":"Soules , C. A. N. , Goodson , G. R. , Strunk , J. D. , and Ganger , G. R . 2003. Metadata efficiency in versioning file systems . In Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST'03) . 43--58. Soules, C. A. N., Goodson, G. R., Strunk, J. D., and Ganger, G. R. 2003. Metadata efficiency in versioning file systems. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST'03). 43--58."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294284"},{"volume-title":"Proceedings of the 17th USENIX Security Symposium.","author":"Sundararaman S.","key":"e_1_2_1_29_1","unstructured":"Sundararaman , S. , Sivathanu , G. , and Zadok , E . 2008. Selective versioning in a secure disk system . In Proceedings of the 17th USENIX Security Symposium. Sundararaman, S., Sivathanu, G., and Zadok, E. 2008. Selective versioning in a secure disk system. In Proceedings of the 17th USENIX Security Symposium."},{"volume-title":"Proceedings of the 19th International Conference on Very Large Data Bases (VLDB'93)","author":"Talens G.","key":"e_1_2_1_30_1","unstructured":"Talens , G. , Oussalah , C. , and Colinas , M. F . 1993. Versions of simple and composite objects . In Proceedings of the 19th International Conference on Very Large Data Bases (VLDB'93) . Talens, G., Oussalah, C., and Colinas, M. F. 1993. Versions of simple and composite objects. In Proceedings of the 19th International Conference on Very Large Data Bases (VLDB'93)."},{"volume-title":"Proceedings of the International Conference on Dependable Systems and Networks.","author":"Zhu N.","key":"e_1_2_1_31_1","unstructured":"Zhu , N. and Chiueh , T . -C. 2003. Design, implementation, and evaluation of repairable file service . In Proceedings of the International Conference on Dependable Systems and Networks. Zhu, N. and Chiueh, T.-C. 2003. Design, implementation, and evaluation of repairable file service. In Proceedings of the International Conference on Dependable Systems and Networks."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1629080.1629083","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1629080.1629083","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:19Z","timestamp":1750278139000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1629080.1629083"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1629080.1629083"],"URL":"https:\/\/doi.org\/10.1145\/1629080.1629083","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2009-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}