Flo: A Semantic Foundation for Progressive Stream Processing

Shadaj Laddad, Alvin Cheung, Joseph M. Hellerstein, Mae Milano

TL;DR

Flo is a new formal foundation for stream processing that unifies diverse systems—from Flink to incremental databases—under a single mathematical framework. By defining two core properties, streaming progress and eager execution, Flo provides a way to prove that streaming programs will remain deterministic and "fresh" regardless of how data is batched or scheduled.

What Problem Does This Paper Address?

The world of stream processing is fragmented. Different systems (like Apache Flink, Spark Streaming, or DBSP) use incompatible data models: some treat streams as ordered sequences, others as sets, lattices, or "Z-sets" (which allow for retractions/deletions).

Because there is no shared semantic foundation, it is difficult to reason about "streamingness" in a general way. Developers often encounter "hanging" programs—for example, accidentally calling a fold operation on an infinite stream, which causes the system to wait forever for a termination signal that never comes. This paper seeks to move beyond "fuzzy" definitions of streaming and provide a precise, type-safe language called Flo that can model almost any existing streaming paradigm.

Methods

The authors introduce Flo, a parameterized streaming language. Its "secret sauce" lies in three main components:

  1. A Parameterized Model: Flo doesn't force you to use a specific data type. It abstracts over "collections" and "operators," allowing it to represent everything from simple lists to complex incremental relations with retractions.
  2. A Lightweight Type System: Flo introduces a boundedness flag (Bounded vs. Unbounded) for stream types. This allows the system to statically ensure that operators only "block" (wait for completion) on streams that are guaranteed to end, preventing infinite hangs.
  3. Core Semantic Properties:
    • Streaming Progress: A guarantee that the system produces as much output as possible given its current input and will never block on an infinite stream.
  4. Eager Execution: A requirement that ensures determinism. It allows a scheduler to process partial data "eagerly" while guaranteeing that the final result is the same as if all data had arrived at once.
  5. Nested Graphs and Cycles: Flo supports "streams of streams" and nested dataflow graphs. This is used to model complex behaviors like windowing (batching data by time) and iterative algorithms (like graph reachability).

Datasets

As a theoretical paper in programming languages and semantics, it does not use traditional training/evaluation datasets. Instead, the "evaluation" consists of formal proofs and three major case studies where the authors demonstrate that Flo can faithfully model the core semantics of:

  • Apache Flink: Modeling windowed aggregations over ordered sequences.
  • LVars: Modeling lattice-based deterministic parallel programming.
  • DBSP: Modeling incremental computation with retractions (Z-sets).

Key Insights and Ideas

  • Streaming is about Progress, not just Types: The authors argue that what makes a system "streaming" isn't the data structure (list vs. set), but the guarantee that it keeps outputs "fresh" relative to inputs without waiting for the end of time.
  • Eagerness = Determinism: By formalizing "eager execution," the authors show that you can give a low-level scheduler immense power to reorder or batch tasks without breaking the program's logic, provided the operators are distributive or monotonic.
  • Boundedness as a First-Class Citizen: Distinguishing between bounded and unbounded streams at the type level catches the most common streaming bug: trying to perform a "final" calculation on a stream that never ends.
  • Unification of Retractions: One of Flo's biggest strengths is its ability to handle retractions (deleting previously sent data), a feature that previous formal models (like "Stream Types") struggled to accommodate.

Key Results

  • Compositional Proofs: The authors prove that if individual operators satisfy "streaming progress" and "eager execution," then any complex graph built from them (including those with parallel/sequential composition and nesting) will also satisfy those properties.
  • Semantic Mapping: The paper successfully maps the specific liveness and correctness goals of Flink, LVars, and DBSP onto Flo’s two core properties. This suggests Flo is a truly "universal" foundation for the field.
  • Safety: The Flo type system successfully identifies "illegal" operators (like a naive LVar-to-sequence converter) that would violate streaming progress or determinism.

Limitations and Future Work

  • Theoretical vs. Practical: Flo is currently a formal calculus and a "paper language." The authors have not yet built a high-performance production compiler or runtime based on it.
  • Operational Abstraction: To keep the semantics clean, Flo abstracts away "real-world" concerns like fault tolerance, distributed state management, and physical network latency.
  • Complex Timestamps: While Flo handles nesting well, modeling extremely complex "time-traveling" systems (like Naiad) might require even more specialized collection types than those presented in the case studies.
  • Future Direction: The authors suggest that Flo could serve as the intermediate representation (IR) for a new generation of streaming compilers that can optimize across different data models (e.g., mixing Flink-style windows with DBSP-style incremental joins).

Summary updated

Abstract

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 "streaming" -- what 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 -- Flink, LVars, and DBSP -- have semantics that can be modeled in Flo and guarantees that map to our properties.
BibTeX
@article{laddad2025flo,
  author = {Shadaj Laddad and Alvin Cheung and Joseph M. Hellerstein and Mae Milano},
  title = {{Flo: A Semantic Foundation for Progressive Stream Processing}},
  journal = {Proc. ACM Program. Lang.},
  year = {2025},
  doi = {10.1145/3704845},
}
Figure