{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T20:31:51Z","timestamp":1760646711800,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2017,10,12]],"date-time":"2017-10-12T00:00:00Z","timestamp":1507766400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2017,10,12]]},"abstract":"<jats:p>Achieving determinism on real software systems remains difficult. Even a batch-processing job, whose task is to map input bits to output bits, risks nondeterminism from thread scheduling, system calls, CPU instructions, and leakage of environmental information such as date or CPU model. In this work, we present a system for achieving low-overhead deterministic execution of batch-processing programs that read and write the file system\u2014turning them into pure functions on files.<\/jats:p>\n          <jats:p>We allow multi-process executions where a permissions system prevents races on the file system. Process separation enables different processes to enforce permissions and enforce determinism using distinct mechanisms. Our prototype, DetFlow, allows a statically-typed coordinator process to use shared-memory parallelism, as well as invoking process-trees of sandboxed legacy binaries. DetFlow currently implements the coordinator as a Haskell program with a restricted I\/O type for its main function: a new monad we call DetIO. Legacy binaries launched by the coordinator run concurrently, but internally each process schedules threads sequentially, allowing dynamic determinism-enforcement with predictably low overhead.<\/jats:p>\n          <jats:p>We evaluate DetFlow by applying it to bioinformatics data pipelines and software build systems. DetFlow enables determinizing these data-processing workflows by porting a small amount of code to become a statically-typed coordinator. This hybrid approach of static and dynamic determinism enforcement permits freedom where possible but restrictions where necessary.<\/jats:p>","DOI":"10.1145\/3133897","type":"journal-article","created":{"date-parts":[[2017,10,13]],"date-time":"2017-10-13T15:15:45Z","timestamp":1507907745000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Monadic composition for deterministic, parallel batch processing"],"prefix":"10.1145","volume":"1","author":[{"given":"Ryan G.","family":"Scott","sequence":"first","affiliation":[{"name":"Indiana University, USA"}]},{"given":"Omar S.","family":"Navarro Leija","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}]},{"given":"Joseph","family":"Devietti","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}]},{"given":"Ryan R.","family":"Newton","sequence":"additional","affiliation":[{"name":"Indiana University, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,10,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/69558.69562"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1924943.1924957"},{"key":"e_1_2_2_3_1","volume-title":"Versioned, P2P File System. CoRR abs\/1407.3561","author":"Benet Juan","year":"2014","unstructured":"Juan Benet . 2014. IPFS - Content Addressed , Versioned, P2P File System. CoRR abs\/1407.3561 ( 2014 ). http:\/\/arxiv.org\/abs\/ 1407.3561 Juan Benet. 2014. IPFS - Content Addressed, Versioned, P2P File System. CoRR abs\/1407.3561 (2014). http:\/\/arxiv.org\/abs\/ 1407.3561"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1924943.1924956"},{"key":"e_1_2_2_5_1","volume-title":"NESL: A Nested Data-Parallel Language. Technical Report CMU-CS-92-103","author":"Blelloch Guy","year":"1992","unstructured":"Guy Blelloch . 1992 . NESL: A Nested Data-Parallel Language. Technical Report CMU-CS-92-103 . Carnegie Mellon University , Pittsburgh, PA . Guy Blelloch. 1992. NESL: A Nested Data-Parallel Language. Technical Report CMU-CS-92-103. Carnegie Mellon University, Pittsburgh, PA."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640097"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22655-7_15"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44898-5_4"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869459.1869515"},{"volume-title":"Modula-3 report (revised)","author":"Cardelli Luca","key":"e_1_2_2_10_1","unstructured":"Luca Cardelli , James Donahue , Lucille Glassman , Mick Jordan , Bill Kalsow , and Greg Nelson . 1989. Modula-3 report (revised) . Vol. 52 . Digital Systems Research Center . Luca Cardelli, James Donahue, Lucille Glassman, Mick Jordan, Bill Kalsow, and Greg Nelson. 1989. Modula-3 report (revised). Vol. 52. Digital Systems Research Center."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248648.1248652"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg500"},{"key":"e_1_2_2_13_1","unstructured":"Douglas Crockford. 2008. ADsafe: Making JavaScript Safe for Advertising. http:\/\/www.adsafe.org\/ . (2008).  Douglas Crockford. 2008. ADsafe: Making JavaScript Safe for Advertising. http:\/\/www.adsafe.org\/ . (2008)."},{"key":"e_1_2_2_14_1","volume-title":"https:\/\/wiki.debian.org\/ReproducibleBuilds?action=recall&amp;rev=339 [Online","author":"Wiki Debian","year":"2016","unstructured":"Debian Wiki . 2016. ReproducibleBuilds. ( 2016 ). https:\/\/wiki.debian.org\/ReproducibleBuilds?action=recall&amp;rev=339 [Online ; accessed 14-April-2017]. Debian Wiki. 2016. ReproducibleBuilds. (2016). https:\/\/wiki.debian.org\/ReproducibleBuilds?action=recall&amp;rev=339 [Online; accessed 14-April-2017]."},{"volume-title":"Eidetic Systems. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201914)","author":"Devecsery David","key":"e_1_2_2_15_1","unstructured":"David Devecsery , Michael Chow , Xianzheng Dou , Jason Flinn , and Peter M. Chen . 2014 . Eidetic Systems. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201914) . USENIX Association, Berkeley, CA, USA, 525\u2013540. http:\/\/dl.acm.org\/citation.cfm?id=2685048.2685090 David Devecsery, Michael Chow, Xianzheng Dou, Jason Flinn, and Peter M. Chen. 2014. Eidetic Systems. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201914). USENIX Association, Berkeley, CA, USA, 525\u2013540. http:\/\/dl.acm.org\/citation.cfm?id=2685048.2685090"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508244.1508255"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950376"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/14.9.755"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542431.1542435"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2011.5749741"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451170"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555252"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594312"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535842"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034675.2034686"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp698"},{"key":"e_1_2_2_28_1","unstructured":"Linux. 2015. ptrace(2) Linux User\u2019s Manual.  Linux. 2015. ptrace(2) Linux User\u2019s Manual."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043587"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863523.1863535"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034675.2034685"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596550.1596563"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037751"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/125826.125861"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741960"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465365"},{"volume-title":"rr: lightweight recording &amp","year":"2015","key":"e_1_2_2_37_1","unstructured":"Mozilla. 2015. rr: lightweight recording &amp ; deterministic debugging. ( 2015 ). http:\/\/rr-project.org\/ [Online; accessed 16-April-2017]. Mozilla. 2015. rr: lightweight recording &amp; deterministic debugging. (2015). http:\/\/rr-project.org\/ [Online; accessed 16-April-2017]."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/292540.292561"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/268998.266669"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/363516.363526"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250746"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541964"},{"volume-title":"Nix: The Purely Functional Package Manager.","year":"2015","key":"e_1_2_2_43_1","unstructured":"Nix. 2015 . Nix: The Purely Functional Package Manager. (2015). https:\/\/nixos.org\/nix\/ [Online; accessed 16-April-2017]. Nix. 2015. Nix: The Purely Functional Package Manager. (2015). https:\/\/nixos.org\/nix\/ [Online; accessed 16-April-2017]."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508244.1508256"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772954.1772958"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301637"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254127"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815411"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796897002943"},{"volume-title":"The Linux Kernel Module Programming Guide. CreateSpace","author":"Salzman Peter Jay","key":"e_1_2_2_50_1","unstructured":"Peter Jay Salzman . 2009. The Linux Kernel Module Programming Guide. CreateSpace , Paramount, CA . Peter Jay Salzman. 2009. The Linux Kernel Module Programming Guide. CreateSpace, Paramount, CA."},{"key":"e_1_2_2_51_1","volume-title":"Introducing mothur: open-source, platformindependent, community-supported software for describing and comparing microbial communities. Applied and environmental microbiology 75, 23","author":"Schloss Patrick D","year":"2009","unstructured":"Patrick D Schloss , Sarah L Westcott , Thomas Ryabin , Justine R Hall , Martin Hartmann , Emily B Hollister , Ryan A Lesniewski , Brian B Oakley , Donovan H Parks , Courtney J Robinson , and others. 2009. Introducing mothur: open-source, platformindependent, community-supported software for describing and comparing microbial communities. Applied and environmental microbiology 75, 23 ( 2009 ), 7537\u20137541. Patrick D Schloss, Sarah L Westcott, Thomas Ryabin, Justine R Hall, Martin Hartmann, Emily B Hollister, Ryan A Lesniewski, Brian B Oakley, Donovan H Parks, Courtney J Robinson, and others. 2009. Introducing mothur: open-source, platformindependent, community-supported software for describing and comparing microbial communities. Applied and environmental microbiology 75, 23 (2009), 7537\u20137541."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/215399.215419"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu033"},{"key":"e_1_2_2_54_1","unstructured":"Ke Sun Xiaoning Li and Ya Ou. 2016. Break Out of the Truman Show: Active Detection and Escape of Dynamic Binary Instrumentation. In Black Hat Asia (Black Hat Asia \u201916). https:\/\/www.blackhat.com\/docs\/asia-16\/materials\/ asia-16-Sun-Break-Out-Of-The-Truman-Show-Active-Detection-And-Escape-Of-Dynamic-Binary-Instrumentation. pdf  Ke Sun Xiaoning Li and Ya Ou. 2016. Break Out of the Truman Show: Active Detection and Escape of Dynamic Binary Instrumentation. In Black Hat Asia (Black Hat Asia \u201916). https:\/\/www.blackhat.com\/docs\/asia-16\/materials\/ asia-16-Sun-Break-Out-Of-The-Truman-Show-Active-Detection-And-Escape-Of-Dynamic-Binary-Instrumentation. pdf"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2011.39"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2364506.2364524"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45937-5_14"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3133897","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3133897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:25Z","timestamp":1750212805000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3133897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,12]]},"references-count":57,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2017,10,12]]}},"alternative-id":["10.1145\/3133897"],"URL":"https:\/\/doi.org\/10.1145\/3133897","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2017,10,12]]},"assertion":[{"value":"2017-10-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}