Modern applications—ranging from self-driving cars and cyber-physical systems to massive data pipelines and IoT networks—rely on the efficient processing of event streams. However, these domains often utilize disparate programming models, making it difficult to reason about system-wide behavior. A primary challenge in these environments is asynchrony. In an asynchronous system, events arrive at unpredictable times, and a scheduler determines the execution order of tasks. If the final output depends on this specific scheduling order, the system becomes non-deterministic and notoriously difficult to debug.
This paper introduces Filter Language (FL), a formal framework that unifies stateful, asynchronous, and probabilistic event processing. Its core contribution is a mathematical guarantee of "scheduler-independence": if individual components are designed correctly, the entire system will produce a consistent result regardless of how the underlying asynchronous scheduler orders tasks.
Methodology: Filters as Transducers
The authors propose modeling programs as directed graphs where nodes are "filters" and edges are "streams." In this framework, each filter is treated as a transducer—a state machine that takes input events, updates its internal state, and produces output events.
Crucially, these transitions can be probabilistic, allowing the model to account for uncertainty, such as a sensor reading that is only 90% certain. To handle the combination of probability and scheduling, the authors employ infinite-state Markov Decision Processes (MDPs). In this model, the "actions" in the MDP represent the choices made by the asynchronous scheduler.
The Property of Local Commutativity
The central innovation of FL is the definition of "local commutativity." A filter is considered commutative if the order in which it processes a set of input events does not change its final state or the total collection of events it outputs.
By ensuring that individual filters possess this property, the authors prove that the entire program achieves confluence. This means that even in a complex, messy asynchronous environment, the distribution of final states is guaranteed to be identical no matter what the scheduler does. This "Aha" moment allows developers to build complex pipelines with the confidence that the underlying execution engine won't introduce non-deterministic bugs.
Unifying Control and Data
One of the most powerful aspects of FL is its ability to bridge the gap between synchronous control languages (often used in safety-critical hardware) and functional data APIs (like Spark or Linq). It treats a Kalman filter used in control theory and a standard map/reduce operation as the same type of mathematical object.
By building probability directly into the transition system, the model can formally reason about algorithms like particle filters that use randomness to estimate the state of the physical world. This unification allows for a single verifiable framework to manage both high-level data processing and low-level hardware control.
Practical Implementation: ThingFlow
Beyond the theoretical proofs, the authors implemented FL as a Python API called ThingFlow. Built on top of Python’s asyncio library, ThingFlow allows developers to build these pipelines in a familiar environment. The API enables easy composition using syntax such as lux.map(...).transduce(...).GpioPinOut(), demonstrating that the formal rigor of FL can be translated into a practical tool for IoT and stream processing.
Key Results and Theorems
The paper presents two flagship results that solidify the framework's utility:
- Theorem 1 (Deterministic Confluence): For deterministic programs, local commutativity implies that the program will always terminate in the same configuration for any two valid schedulers.
- Theorem 2 (Probabilistic Confluence): This result extends the proof to the probabilistic setting, showing that for a locally confluent probabilistic FL program, the probability distribution over final states is invariant across all schedulers that terminate almost surely.
Limitations and Future Work
While FL provides a robust theoretical foundation, several challenges remain. Currently, there is no automated static analysis tool to check if a ThingFlow program is scheduler-independent; developers must ensure local commutativity manually. Furthermore, existing "off-the-shelf" verification tools are not yet fully equipped to handle the infinite-state hybrid probabilistic problems posed by FL.
Future research directions include developing these verification tools and exploring "denotational" semantics—mathematically defining what a program is rather than just how it moves step-by-step—using concepts like "arrows" from functional reactive programming.
Summary updated