{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:44:46Z","timestamp":1780994686896,"version":"3.54.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T00:00:00Z","timestamp":1736208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000015","name":"DOE U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0016260"],"award-info":[{"award-number":["DE-SC0016260"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1730628, IIS-1955488, IIS-2027575, DGE-2146752"],"award-info":[{"award-number":["CCF-1730628, IIS-1955488, IIS-2027575, DGE-2146752"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,1,7]]},"abstract":"<jats:p>Streaming systems are present throughout modern applications, processing continuous data in real-time. Existing streaming languages have a variety of semantic models and guarantees that are often incompatible. Yet all these languages are considered \u201cstreaming\u201d\u2013what do they have in common? In this paper, we identify two general yet precise semantic properties: streaming progress and eager execution. Together, they ensure that streaming outputs are deterministic and kept fresh with respect to streaming inputs. We formally define these properties in the context of Flo, a parameterized streaming language that abstracts over dataflow operators and the underlying structure of streams. It leverages a lightweight type system to distinguish bounded streams, which allow operators to block on termination, from unbounded ones. Furthermore, Flo provides constructs for dataflow composition and nested graphs with cycles. To demonstrate the generality of our properties, we show how key ideas from representative streaming and incremental computation systems\u2014Flink, LVars, and DBSP\u2014have semantics that can be modeled in Flo and guarantees that map to our properties.<\/jats:p>","DOI":"10.1145\/3704845","type":"journal-article","created":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T05:48:42Z","timestamp":1736401722000},"page":"241-270","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Flo: A Semantic Foundation for Progressive Stream Processing"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6658-6548","authenticated-orcid":false,"given":"Shadaj","family":"Laddad","sequence":"first","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6261-6263","authenticated-orcid":false,"given":"Alvin","family":"Cheung","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7712-4306","authenticated-orcid":false,"given":"Joseph M.","family":"Hellerstein","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3126-7771","authenticated-orcid":false,"given":"Mae","family":"Milano","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,1,9]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"277","article-title":"The design of the borealis stream processing engine.","volume":"5","author":"Abadi Daniel J","year":"2005","unstructured":"Daniel J Abadi, Yanif Ahmad, Magdalena Balazinska, Ugur Cetintemel, Mitch Cherniack, Jeong-Hyon Hwang, Wolfgang Lindner, Anurag Maskey, Alex Rasin, Esther Ryvkina, et al. 2005. The design of the borealis stream processing engine.. In Cidr, Vol. 5. 277\u2013289.","journal-title":"Cidr"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0095-z"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824076"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824076"},{"key":"e_1_3_2_6_2","unstructured":"Peter Alvaro Neil Conway Joseph M Hellerstein and William R Marczak. 2011. Consistency Analysis in Bloom: a CALM and Collected Approach.. In CIDR. Citeseer 249\u2013260."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9_16"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0147-z"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0147-z"},{"key":"e_1_3_2_10_2","first-page":"28","article-title":"Semina\u00efve evaluation for a higher-order functional language","volume":"4","author":"Arntzenius Michael","year":"2019","unstructured":"Michael Arntzenius and Neel Krishnaswami. 2019. Semina\u00efve evaluation for a higher-order functional language. Proc. ACM Program. Lang. 4, POPL, Article 22 (dec 2019), 28 pages. https:\/\/doi.org\/10.1145\/3371090 10.1145\/3371090","journal-title":"Proc. ACM Program. Lang."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872789"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/603867.603884"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"G\u00e9rard Berry and Laurent Cosserat. 1985. The ESTEREL synchronous programming language and its mathematical semantics. In Seminar on Concurrency: Carnegie-Mellon University Pittsburgh PA July 9-11 1984. Springer 389\u2013448.","DOI":"10.1007\/3-540-15670-4_19"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587137"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","unstructured":"Paris Carbone Marios Fragkoulis Vasiliki Kalavri and Asterios Katsifodimos. 2020. Beyond analytics: The evolution of stream processing systems. In Proceedings of the 2020 ACM SIGMOD international conference on Management of data. 2651\u20132658.","DOI":"10.1145\/3318464.3383131"},{"issue":"4","key":"e_1_3_2_16_2","article-title":"Apache flink: Stream and batch processing in a single engine","volume":"38","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache flink: Stream and batch processing in a single engine. The Bulletin of the Technical Committee on Data Engineering 38, 4 (2015).","journal-title":"The Bulletin of the Technical Committee on Data Engineering"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315523"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/41625.41641"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535881"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3656434"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670995"},{"key":"e_1_3_2_22_2","first-page":"213","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","author":"Gjengset Jon","year":"2018","unstructured":"Jon Gjengset, Malte Schwarzkopf, Jonathan Behrens, Lara Timb\u00f3 Ara\u00fajo, Martin Ek, Eddie Kohler, M. Frans Kaashoek, and Robert Morris. 2018. Noria: dynamic, partially-stateful data-flow for high-performance web applications. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). USENIX Association, Carlsbad, CA, 213\u2013231. https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/gjengset"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594324"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/1624775.1624804"},{"key":"e_1_3_2_25_2","volume-title":"Mastering apache storm: Real-time big data streaming using kaf ka, hbase and redis","author":"Jain Ankit","year":"2017","unstructured":"Ankit Jain. 2017. Mastering apache storm: Real-time big data streaming using kaf ka, hbase and redis. Packt Publishing Ltd."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2103776.2103783"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603106"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2544174.2500588"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3315507.3330199"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742788"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2502323.2502326"},{"key":"e_1_3_2_32_2","volume-title":"Building Big Data Pipelines with Apache Beam: Use a single programming model for both batch and stream data processing","author":"Lukavsky Jan","year":"2022","unstructured":"Jan Lukavsky. 2022. Building Big Data Pipelines with Apache Beam: Use a single programming model for both batch and stream data processing. Packt Publishing Ltd."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-44914-8_15"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314580"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2460756.2460762"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137770"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213890"},{"key":"e_1_3_2_39_2","unstructured":"Jennifer Paykin Neelakantan R Krishnaswami and Steve Zdancewic. 2016. The essence of event-driven programming. Leibniz Leibniz International Proceedings in Informatics (2016)."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3639271"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11957-6_27"},{"key":"e_1_3_2_42_2","doi-asserted-by":"crossref","unstructured":"Utkarsh Srivastava and Jennifer Widom. 2004. Flexible time management in data stream systems. In Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 263\u2013274.","DOI":"10.1145\/1055558.1055596"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45937-5_14"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198390"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/103135.103137"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522737"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3704845","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3704845","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T10:15:02Z","timestamp":1770200102000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3704845"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,7]]},"references-count":45,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2025,1,7]]}},"alternative-id":["10.1145\/3704845"],"URL":"https:\/\/doi.org\/10.1145\/3704845","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,7]]},"assertion":[{"value":"2024-07-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}