{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:13:05Z","timestamp":1761401585713,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,1,11]],"date-time":"2012-01-11T00:00:00Z","timestamp":1326240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGOPS Oper. Syst. Rev."],"published-print":{"date-parts":[[2012,1,11]]},"abstract":"<jats:p>A common assumption made in log analysis research is that the underlying log is totally ordered. For concurrent systems, this assumption constrains the generated log to either exclude concurrency altogether, or to capture a particular interleaving of concurrent events. This paper argues that capturing concurrency as a partial order is useful and often indispensable for answering important questions about concurrent systems. To this end, we motivate a family of event ordering invariants over partially ordered event traces, give three algorithms for mining these invariants from logs, and evaluate their scalability on simulated distributed system logs.<\/jats:p>","DOI":"10.1145\/2094091.2094101","type":"journal-article","created":{"date-parts":[[2012,1,17]],"date-time":"2012-01-17T17:21:44Z","timestamp":1326820904000},"page":"39-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Mining temporal invariants from partially ordered logs"],"prefix":"10.1145","volume":"45","author":[{"given":"Ivan","family":"Beschastnikh","sequence":"first","affiliation":[{"name":"University of Washington"}]},{"given":"Yuriy","family":"Brun","sequence":"additional","affiliation":[{"name":"University of Washington"}]},{"given":"Michael D.","family":"Ernst","sequence":"additional","affiliation":[{"name":"University of Washington"}]},{"given":"Arvind","family":"Krishnamurthy","sequence":"additional","affiliation":[{"name":"University of Washington"}]},{"given":"Thomas E.","family":"Anderson","sequence":"additional","affiliation":[{"name":"University of Washington"}]}],"member":"320","published-online":{"date-parts":[[2012,1,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0164-1212(83)90011-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.12.012"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025151"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"e_1_2_1_5_1","first-page":"181","volume-title":"First International Conference, ADB-94","volume":"819","author":"CONSENS M. C.","year":"1993","unstructured":"CONSENS , M. C. , HASAN , M. Z. , AND MENDELZON , A. O. Debugging Distributed Programs by Visualizing and Querying Event Traces. In Applications of Databases , First International Conference, ADB-94 ( 1993 ), vol. 819 , pp. 181 -- 183 . CONSENS, M. C., HASAN, M. Z., AND MENDELZON, A. O. Debugging Distributed Programs by Visualizing and Querying Event Traces. In Applications of Databases, First International Conference, ADB-94 (1993), vol. 819, pp. 181--183."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00722-4_8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/302405.302672"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.908957"},{"key":"e_1_2_1_9_1","first-page":"55","volume-title":"11th Australian Computer Science Conference","author":"FIDGE C. J.","year":"1988","unstructured":"FIDGE , C. J. Timestamps in Message-Passing Systems that Preserve the Partial Ordering . In 11th Australian Computer Science Conference ( University of Queensland, Australia , 1988 ), pp. 55 -- 66 . FIDGE, C. J. Timestamps in Message-Passing Systems that Preserve the Partial Ordering. In 11th Australian Computer Science Conference (University of Queensland, Australia, 1988), pp. 55--66."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1453101.1453150"},{"key":"e_1_2_1_12_1","first-page":"372","volume-title":"W. CADP 2010: A Toolbox for the Construction and Analysis of Distributed Processes. In Tools and Algorithms for the Construction and Analysis of Systems, P. Abdulla and K. Leino, Eds.","volume":"6605","author":"GARAVEL H.","year":"2011","unstructured":"GARAVEL , H. , LANG , F. , MATEESCU , R. , AND SERWE , W. CADP 2010: A Toolbox for the Construction and Analysis of Distributed Processes. In Tools and Algorithms for the Construction and Analysis of Systems, P. Abdulla and K. Leino, Eds. , vol. 6605 of Lecture Notes in Computer Science. Springer Berlin \/ Heidelberg, Berlin, Heidelberg , 2011 , ch. 33, pp. 372 -- 387 . GARAVEL, H., LANG, F., MATEESCU, R., AND SERWE, W. CADP 2010: A Toolbox for the Construction and Analysis of Distributed Processes. In Tools and Algorithms for the Construction and Analysis of Systems, P. Abdulla and K. Leino, Eds., vol. 6605 of Lecture Notes in Computer Science. Springer Berlin \/ Heidelberg, Berlin, Heidelberg, 2011, ch. 33, pp. 372--387."},{"key":"e_1_2_1_13_1","volume-title":"Networked Systems Design and Implementation (NSDI)","author":"GEELS D.","year":"2007","unstructured":"GEELS , D. , ALTEKAR , G. , MANIATIS , P. , ROSCOE , T. , AND STOICA , I. Friday: Global Comprehension for Distributed Replay . In Networked Systems Design and Implementation (NSDI) ( 2007 ). GEELS, D., ALTEKAR, G., MANIATIS, P., ROSCOE, T., AND STOICA, I. Friday: Global Comprehension for Distributed Replay. In Networked Systems Design and Implementation (NSDI) (2007)."},{"key":"e_1_2_1_14_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-09526-8_27","volume-title":"Mathematical Foundations of Computer Science","author":"GORALCIKOVA A.","year":"1979","unstructured":"GORALCIKOVA , A. , AND KOUBEK , V. A Reduct-and-Closure Algorithm for Graphs . In Mathematical Foundations of Computer Science 1979 , J. Becvar, Ed ., vol. 74 of Lecture Notes in Computer Science . Springer Berlin \/ Heidelberg , 1979, pp. 301 -- 307 . GORALCIKOVA, A., AND KOUBEK, V. A Reduct-and-Closure Algorithm for Graphs. In Mathematical Foundations of Computer Science 1979, J. Becvar, Ed., vol. 74 of Lecture Notes in Computer Science. Springer Berlin \/ Heidelberg, 1979, pp. 301--307."},{"key":"e_1_2_1_15_1","unstructured":"Welcome to Apache Hadoop! http:\/\/hadoop.apache.org\/. Accessed April 6 2011.  Welcome to Apache Hadoop! http:\/\/hadoop.apache.org\/. Accessed April 6 2011."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICAC.2005.42"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190648"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation","author":"LIU X.","year":"2008","unstructured":"LIU , X. , GUO , Z. , WANG , X. , CHEN , F. , LIAN , X. , TANG , J. , WU , M. , KAASHOEK , M. F. , AND ZHANG , Z. D3S : Debugging Deployed Distributed Systems . In Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation ( Berkeley, CA, USA , 2008 ), NSDI'08, USENIX Association, pp. 423--437. LIU, X., GUO, Z., WANG, X., CHEN, F., LIAN, X., TANG, J., WU, M., KAASHOEK, M. F., AND ZHANG, Z. D3S: Debugging Deployed Distributed Systems. In Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation (Berkeley, CA, USA, 2008), NSDI'08, USENIX Association, pp. 423--437."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835883"},{"key":"e_1_2_1_20_1","first-page":"215","volume-title":"Parallel and Distributed Algorithms","author":"MATTERN F.","year":"1989","unstructured":"MATTERN , F. Virtual Time and Global States of Distributed Systems . In Parallel and Distributed Algorithms ( 1989 ), pp. 215 -- 226 . MATTERN, F. Virtual Time and Global States of Distributed Systems. In Parallel and Distributed Algorithms (1989), pp. 215--226."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629585"},{"key":"e_1_2_1_22_1","first-page":"9","volume-title":"A. Pip: Detecting the Unexpected in Distributed Systems. In Proceedings of the 3rd conference on Networked Systems Design & Implementation -","volume":"3","author":"REYNOLDS P.","year":"2006","unstructured":"REYNOLDS , P. , KILLIAN , C. , WIENER , J. L. , MOGUL , J. C. , SHAH , M. A. , AND VAHDAT , A. Pip: Detecting the Unexpected in Distributed Systems. In Proceedings of the 3rd conference on Networked Systems Design & Implementation - Volume 3 (Berkeley, CA, USA, 2006 ), NSDI'06, USENIX Association , p. 9 . REYNOLDS, P., KILLIAN, C., WIENER, J. L., MOGUL, J. C., SHAH, M. A., AND VAHDAT, A. Pip: Detecting the Unexpected in Distributed Systems. In Proceedings of the 3rd conference on Networked Systems Design & Implementation - Volume 3 (Berkeley, CA, USA, 2006), NSDI'06, USENIX Association, p. 9."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 16th International Parallel and Distributed Processing Symposium (Washington","author":"SEN A.","year":"2002","unstructured":"SEN , A. , AND GARG , V. K. Detecting Temporal Logic Predicates on the Happened-Before Model . In Proceedings of the 16th International Parallel and Distributed Processing Symposium (Washington , DC, USA , 2002 ), IPDPS '02, IEEE Computer Society . SEN, A., AND GARG, V. K. Detecting Temporal Logic Predicates on the Happened-Before Model. In Proceedings of the 16th International Parallel and Distributed Processing Symposium (Washington, DC, USA, 2002), IPDPS '02, IEEE Computer Society."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/69215.69237"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the First USENIX conference on Analysis of system logs","author":"TAN J.","year":"2008","unstructured":"TAN , J. , PAN , X. , KAVULYA , S. , GANDHI , R. , AND NARASIMHAN , P. SALSA : Analyzing Logs as State Machines . In Proceedings of the First USENIX conference on Analysis of system logs ( Berkeley, CA, USA , 2008 ), WASL'08, USENIX Association, p. 6. TAN, J., PAN, X., KAVULYA, S., GANDHI, R., AND NARASIMHAN, P. SALSA: Analyzing Logs as State Machines. In Proceedings of the First USENIX conference on Analysis of system logs (Berkeley, CA, USA, 2008), WASL'08, USENIX Association, p. 6."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 2009 conference on Hot topics in cloud computing","author":"TAN J.","year":"2009","unstructured":"TAN , J. , PAN , X. , KAVULYA , S. , GANDHI , R. , AND NARASIMHAN , P. Mochi : Visual Log-analysis based Tools for Debugging Hadoop . In Proceedings of the 2009 conference on Hot topics in cloud computing ( Berkeley, CA, USA , 2009 ), HotCloud'09, USENIX Association, p. 18. TAN, J., PAN, X., KAVULYA, S., GANDHI, R., AND NARASIMHAN, P. Mochi: Visual Log-analysis based Tools for Debugging Hadoop. In Proceedings of the 2009 conference on Hot topics in cloud computing (Berkeley, CA, USA, 2009), HotCloud'09, USENIX Association, p. 18."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30179-0_27"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629587"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SRDS.2011.29"},{"key":"e_1_2_1_30_1","volume-title":"V. CrystalBall: Predicting and Preventing Inconsistencies in Deployed Distributed Systems. In Proceedings of the 6th USENIX symposium on Networked systems design and implementation","author":"YABANDEH M.","year":"2009","unstructured":"YABANDEH , M. , KNEZEVIC , N. , KOSTI'C , D. , AND KUNCAK , V. CrystalBall: Predicting and Preventing Inconsistencies in Deployed Distributed Systems. In Proceedings of the 6th USENIX symposium on Networked systems design and implementation ( Berkeley, CA, USA , 2009 ), USENIX Association, pp. 229--244. YABANDEH, M., KNEZEVIC, N., KOSTI'C , D., AND KUNCAK, V. CrystalBall: Predicting and Preventing Inconsistencies in Deployed Distributed Systems. In Proceedings of the 6th USENIX symposium on Networked systems design and implementation (Berkeley, CA, USA, 2009), USENIX Association, pp. 229--244."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSRE.2004.11"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/996821.996832"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735970.1736038"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1740390.1740410"}],"container-title":["ACM SIGOPS Operating Systems Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2094091.2094101","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2094091.2094101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:48:41Z","timestamp":1750240121000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2094091.2094101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,11]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,1,11]]}},"alternative-id":["10.1145\/2094091.2094101"],"URL":"https:\/\/doi.org\/10.1145\/2094091.2094101","relation":{},"ISSN":["0163-5980"],"issn-type":[{"type":"print","value":"0163-5980"}],"subject":[],"published":{"date-parts":[[2012,1,11]]},"assertion":[{"value":"2012-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}