{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T04:57:37Z","timestamp":1755838657418,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2017,12,27]],"date-time":"2017-12-27T00:00:00Z","timestamp":1514332800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Random testing has proven to be an effective way to catch bugs in distributed systems in the presence of network partition faults. This is surprising, as the space of potentially faulty executions is enormous, and the bugs depend on a subtle interplay between sequences of operations and faults.<\/jats:p>\n          <jats:p>We provide a theoretical justification of the effectiveness of random testing in this context. First, we show a general construction, using the probabilistic method from combinatorics, that shows that whenever a random test covers a fixed coverage goal with sufficiently high probability, a small randomly-chosen set of tests achieves full coverage with high probability. In particular, we show that our construction can give test sets exponentially smaller than systematic enumeration. Second, based on an empirical study of many bugs found by random testing in production distributed systems, we introduce notions of test coverage relating to network partition faults which are effective in finding bugs. Finally, we show using combinatorial arguments that for these notions of test coverage we introduce, we can find a lower bound on the probability that a random test covers a given goal. Our general construction then explains why random testing tools achieve good coverage---and hence, find bugs---quickly.<\/jats:p>\n          <jats:p>While we formulate our results in terms of network partition faults, our construction provides a step towards rigorous analysis of random testing algorithms, and can be applicable in other scenarios.<\/jats:p>","DOI":"10.1145\/3158134","type":"journal-article","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T14:21:49Z","timestamp":1514557309000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Why is random testing effective for partition tolerance bugs?"],"prefix":"10.1145","volume":"2","author":[{"given":"Rupak","family":"Majumdar","sequence":"first","affiliation":[{"name":"MPI-SWS, Germany"}]},{"given":"Filip","family":"Niksic","sequence":"additional","affiliation":[{"name":"MPI-SWS, Germany"}]}],"member":"320","published-online":{"date-parts":[[2017,12,27]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_2_1_1","DOI":"10.1007\/978-3-0346-0425-3_1"},{"volume-title":"Spencer","year":"2004","author":"Alon Noga","key":"e_1_2_2_2_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_3_1","DOI":"10.1145\/2723372.2723711"},{"volume-title":"Fault Injection Framework and Development Guide. Retrieved","year":"2017","author":"Hadoop Apache","key":"e_1_2_2_4_1"},{"volume-title":"Principles of Model Checking","author":"Baier Christel","key":"e_1_2_2_5_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_6_1","DOI":"10.1145\/343477.343502"},{"volume-title":"Retrieved","year":"2017","author":"Brewer Eric A.","key":"e_1_2_2_7_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_8_1","DOI":"10.1145\/1736020.1736040"},{"volume-title":"Principles of Chaos Engineering. Retrieved","year":"2017","author":"Engineering Chaos","key":"e_1_2_2_9_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_10_1","DOI":"10.1007\/978-3-319-41540-6_9"},{"volume-title":"Proceeding of the 14th ACM SIGPLAN international conference on Functional programming, ICFP 2009. ACM, 149\u2013160","author":"Claessen Koen","key":"e_1_2_2_11_1"},{"key":"e_1_2_2_12_1","first-page":"125","article-title":"Combinatorial aspects of covering arrays","volume":"59","author":"Colbourn Charles J.","year":"2004","journal-title":"Le Matematiche"},{"doi-asserted-by":"publisher","key":"e_1_2_2_13_1","DOI":"10.1016\/S0304-3975(96)00146-6"},{"volume-title":"14th USENIX Conference on File and Storage Technologies, FAST 2016","year":"2016","author":"Deligiannis Pantazis","key":"e_1_2_2_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_15_1","DOI":"10.2307\/2371374"},{"doi-asserted-by":"publisher","key":"e_1_2_2_16_1","DOI":"10.4169\/amer.math.monthly.124.2.179"},{"doi-asserted-by":"publisher","key":"e_1_2_2_17_1","DOI":"10.1007\/978-3-540-78800-3_22"},{"doi-asserted-by":"publisher","key":"e_1_2_2_18_1","DOI":"10.1145\/828.1884"},{"doi-asserted-by":"publisher","key":"e_1_2_2_19_1","DOI":"10.1145\/564585.564601"},{"volume-title":"Sunley","year":"1996","author":"Godbole Anant P.","key":"e_1_2_2_20_1"},{"volume-title":"Donald Ervin Knuth, and Oren Patashnik","year":"1994","author":"Graham Ronald L.","key":"e_1_2_2_21_1"},{"volume-title":"Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2011","year":"2011","author":"Gunawi Haryadi S.","key":"e_1_2_2_22_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_23_1","DOI":"10.1145\/2815400.2815428"},{"volume-title":"The Netflix Simian Army. Retrieved","year":"2017","author":"Izrailevsky Yury","key":"e_1_2_2_24_1"},{"volume-title":"Partitions for Everyone! Retrieved","year":"2017","author":"Kingsbury Kyle","key":"e_1_2_2_25_1"},{"unstructured":"Kyle Kingsbury. 2013\u20132017. Jepsen. Retrieved July 7 2017 from http:\/\/jepsen.io\/  Kyle Kingsbury. 2013\u20132017. Jepsen. Retrieved July 7 2017 from http:\/\/jepsen.io\/","key":"e_1_2_2_26_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_27_1","DOI":"10.1016\/j.ic.2016.03.006"},{"volume-title":"Encyclopedia of Software Engineering, Phillip A","author":"Kuhn D. Richard","key":"e_1_2_2_28_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_29_1","DOI":"10.1109\/FMCAD.2008.ECP.29"},{"doi-asserted-by":"publisher","key":"e_1_2_2_30_1","DOI":"10.1145\/177492.177726"},{"volume-title":"SAMC: Semantic-Aware Model Checking for Fast Discovery of Deep Bugs in Cloud Systems. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI \u201914","year":"2014","author":"Leesatapornwongsa Tanakorn","key":"e_1_2_2_31_1"},{"volume-title":"Markov Chains and Mixing Times","author":"Levin David Asher","key":"e_1_2_2_32_1"},{"volume-title":"Distributed Systems Testing: The Lost World. Retrieved","year":"2017","author":"Lopes Cristina Videira","key":"e_1_2_2_33_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_34_1","DOI":"10.1145\/2857274.2889274"},{"doi-asserted-by":"publisher","key":"e_1_2_2_35_1","DOI":"10.1007\/3-540-58179-0_49"},{"volume-title":"2014 USENIX Annual Technical Conference, USENIX ATC \u201914","year":"2014","author":"Ongaro Diego","key":"e_1_2_2_36_1"},{"volume-title":"Technologies for Testing and Debugging Distributed Systems. Retrieved","year":"2017","author":"Scott Colin","key":"e_1_2_2_37_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_38_1","DOI":"10.1109\/18.6031"},{"doi-asserted-by":"publisher","key":"e_1_2_2_39_1","DOI":"10.1145\/75246.75276"},{"doi-asserted-by":"publisher","key":"e_1_2_2_40_1","DOI":"10.1145\/2737924.2737958"},{"volume-title":"Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2009","year":"2009","author":"Yang Junfeng","key":"e_1_2_2_41_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_42_1","DOI":"10.1137\/0603036"},{"doi-asserted-by":"publisher","key":"e_1_2_2_43_1","DOI":"10.1145\/322261.322274"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158134","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158134","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:30Z","timestamp":1750212690000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,27]]},"references-count":43,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1145\/3158134"],"URL":"https:\/\/doi.org\/10.1145\/3158134","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2017,12,27]]},"assertion":[{"value":"2017-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}