CS Paper Radar

Designing a Producer-driven Stream Protocol by Formal Refinement

Erick Lavoie

cs.PL ·submitted 2026-09-27 18:07 UTC · v1

Abstract

The coroutine has broadly diffused in the practice of concurrent programming in the form of generators and asynchronous functions as well as processes communicating through pipes. We wanted to use coroutines in Python to create single-threaded Unix-style pipelines. Unfortunately, available solutions in Python are cumbersome to use. The JavaScript push-stream protocol appeared to be a good alternative. However, its specification is incomplete and ambiguous. We have used TLA$^{+}$ and the TLC model checker to re-derive the protocol and obtain protocol-specific verification tools. In this paper, we present a formal specification of a push-stream protocol that 1) seamlessly combines synchronous and asynchronous modules, encapsulating the choice within each module; 2) provides flow control without using bounded buffers; 3) gracefully and unambiguously terminates; 4) does not require dynamic allocation of objects on the heap. In addition to completely describing expected behaviours, our specification improves on the original design by 1) allowing the input and output of intermediate pipeline modules to terminate independently and 2) explicitly reporting when a module is pending on the execution environment, to avoid incorrect resuming. We specify the protocol as a sequence of refinement steps and derive by equivalence a specification of what an abstract module may do. We then refine the latter into a module checker that can verify concrete module specifications for conformity. We have verified the key properties of all specifications and the validity of refinement steps with TLC. In supplemental material, we provide all TLA$^{+}$ specifications, show that the protocol is sufficiently expressive to implement a superset of all original JavaScript modules, as well as a performance comparison with Python alternatives and Unix pipes.

Closest papers

Nearest neighbours by meaning across the whole index.

Modular Responsiveness Verification of Rust Async Runtimes

cs.PL ·2026-10-06 ·Yanze Li, Ivan Beschastnikh, Alexander J. Summers
published similarity 0.63
Abstract · To appear at ESOP 2027, preprint with appendix

Asynchronous (async) programming is a popular paradigm for managing concurrency. Languages that provide async support typically have a runtime to manage asynchronous executions. These runtimes are critical infrastructure, yet verifying them has received little attention. One reason is that a property that users care most about from an async runtime is a liveness property: tasks submitted to the runtime eventually make progress. Verifying liveness is challenging for libraries that are both concurrent and highly optimized. We present a lightweight and modular proof technique for verifying eventual progression guarantees for Rust async runtimes. We describe this technique in the context of a simple language based on Rust and Rust's async model. We then realize this proof technique as a set of static analyses for Rust and use these to verify eventual progression of several key components of multiple Rust async runtime implementations.

0.19

On the Expressiveness of Asynchronous Processes with Nested Session Types (Extended Version)

cs.PL cs.DC ·2026-10-23 ·Sjors Wortelboer, Dan Frumin, Jorge A. Pérez
theory similarity 0.60
Abstract · Extended version of a paper submitted to EXPRESS/SOS 2026

Session types are a type-based approach to correct message-passing programs, where types specify protocols for channels and type checking guarantees communication correctness. Traditional session types express regular protocols only, which leaves out many protocols found in practice. Aiming at overcoming this limitation, Nested Session Types (NSTs) can specify nested recursive protocols. NSTs are known to be characterised by one-counter machines and deterministic context-free languages. In this paper, we study the expressiveness of ASP (Asynchronous Session Processes), the process model associated with NSTs as introduced by Das et al. We prove that AST is Turing complete by giving a correct encoding of two-counter machines into typed processes. Our encoding uses a non-trivial state-aware representation of counters and instructions that is neatly governed by NSTs.

0.34

A Type System for Communication-Safe Hardware Design

cs.PL cs.ARcs.LO ·2026-10-19 ·Aditya Ranjan Jha, Jason Zhijingcheng Yu, Umang Mathur, Prateek Saxena
top venuecode/data similarity 0.60
Abstract · 69 pages, 4 figures, 3 tables. Conditionally accepted to POPL 2027

Hardware components communicate through clock-cycle-sensitive protocols. Hardware Description Languages (HDLs), however, provide limited support for expressing these protocols or for checking that independently developed components agree on them. When components disagree, the composed design can perform unsynchronized exchanges or stop making progress. We call these failures communication-safety violations. Communication safety is thus a global property, determined by interactions between components. This makes it difficult to check modularly. This paper presents Pact, a typed extension of Anvil for modular verification of communication safety in synchronous hardware. Pact types describe message-passing, control-flow, and clock-cycle behaviour. Each component is checked against its type. Compatible types guarantee that the components compose into a communication-safe system. Pact also supports incremental design. It can check a subsystem before the rest of the system exists. The check produces a summary type that captures the communication behaviour left for future compositions. To reduce annotation burden, Pact infers types by abstracting payload values while preserving communication, timing, control, and fairness. These inferred types are optimal for the checker: whenever some checker-accepted types can prove compatibility, the inferred types can prove it as well. Type inference and type checking are decidable, and compatibility is decided by a sound and complete algorithm. We implement Pact by extending the Anvil compiler and evaluate it along five dimensions: detecting communication errors in incremental design, expressiveness on ten clock-cycle-accurate translations of open-source hardware IPs, compatibility-checking time, generated hardware overhead, and annotation burden. Pact expresses realistic protocols and verifies all ten benchmarks in reasonable time.

0.73

Koala: Non-disruptive Reconfiguration for Long-running Stateful Dataflows

cs.DC ·2026-10-20 ·Lei Huang, Sakshi Sharma, Chenxu Yu, Zikun Wang, Yuanli Wang +3 more
similarity 0.59
Abstract

Stateful dataflow systems must decide where state lives relative to the tasks that process it. For long-running applications that require frequent reconfiguration due to changes in resource allocation, partitioning, or task placement, this design choice presents a core trade-off between adaptability and performance. Co-locating state with computation ensures low latency at steady state but makes reconfiguration disruptive, as any change forces state migration. On the other hand, keeping state in an external store makes reconfiguration seamless, but incurs overhead on every access. We present Koala, a reconfiguration protocol for distributed dataflow systems that retains the operational performance of embedded-state architectures while matching the disruption-free adaptability of external-state designs. Unlike prior protocols which relocate all state regardless of whether it will soon be accessed, Koala migrates state in a fine-grained, lazy manner. To achieve that, it employs a lightweight ownership transfer mechanism that safely decouples event routing from state location. We implement Koala in a new streaming dataflow system and evaluate it on real-world and synthetic benchmarks. When compared with the state-of-the-art protocol DRRS, Koala consumes backlog up to 23x faster and transfers 8.7x less state on average during reconfiguration.

0.21

Specifying Paxos for System Builders: Pseudocode Made Executable

cs.DC ·2026-09-10 ·Yanhong A. Liu, Rahul Sihag
similarity 0.59
Abstract · 41 pages. Extended version of invited paper at the 28th International Symposium on Stabilization, Safety, and Security of Distributed System…

This paper presents a precise executable specification---as a faithful mapping from the pseudocode---of Paxos for System Builders, a practical protocol for replication and consensus in distributed systems. Paxos for System Builders has both a robust implementation in C and a clean pseudocode for critical protocol details. This paper shows how the protocol pseudocode can be expressed easily, essentially line-by-line, in a precise high-level language, DistAlgo, for direct execution in distributed systems. Precise specification and direct execution help significantly in understanding the protocol logic and in automatically checking, tracing, and visualizing protocol runs. They also led to discoveries and fixes of small, difficult-to-catch omissions and liveness bugs in the pseudocode though not the C code. The resulting program also has acceptable performance while having similar size as the pseudocode.

0.26

Coexponential Exploration in the Clef Programming Language

cs.PL cs.DCcs.LO ·2026-10-09 ·Houston Haynes
theory similarity 0.58
Abstract · 36 pages, 4 figures, 3 tables. Updated for contributions from Karwowski et al. and clarified Padovani's fair-termination result

Clef was created as a concurrent programming language whose compiler tracks state ownership, waiting computations and request dependencies. We develop a coexponential account of stateful services and their client pools within this design. Delimited continuations retain the computation and resources needed to complete each interaction. These structures give our compiler premises for verifying service composition and preserving it through native lowering to multiple hardware targets. We connect finite actor state transitions to the initial, service and final rules of a coexponential server. A separate operational account relates actor dispatch to single-use continuation frames. We prove state-ownership and reply preservation, give a finite communication-summary analysis, and derive circular-wait exclusion under stated assumptions. A further result identifies when changing service order preserves both state and replies. Our Program Semantic Graph retains these facts through compilation. We are researching reusable proofs to confirm the ownership and communication interfaces, while our BAREWire implementation connects message meaning to its unboxed representation across respective endpoints. A distributed worker example preserves request identity across suspension, reordered replies and boundary conversion. Urschel's growth bounds inform a solver service; a distributed ADM update additionally preserves joint samples, metric evidence and request identity. Our two-category account connects component refinement, reusable proof terms and native realization. Protocols determine the admissible interactions, continuations expose their storage requirements, and retained dependencies support differential compilation. Developers can express ordinary stateful services while the compiler carries the conditions for their correct composition across execution targets.

0.19

Compiling Imperative Hardware Protocol Specifications to Hardware

cs.PL ·2026-11-14 ·Nikil V. Shyamsunder, Ernest Ng, Adrian Sampson, Kevin Laeufer
similarity 0.58
Abstract · 28 pages, 16 figures

Correct modular composition in hardware depends on interfaces with subtle multi-cycle timing behavior, yet such protocols remain difficult to specify, test, and debug. Recent work has demonstrated that hardware communication specifications can take the form of compact imperative programs that describe the cycle-by-cycle behavior of each logical transaction. However, prior tools only use these specifications for simulation-based testing and debugging, and their semantics remain informal. In this work, we develop a theory of hardware protocol specifications using automata. In addition to making the specifications' meaning precise, the automaton representation lets us compile them into synthesizable hardware. We implement a compiler that produces RTL modules for driving hardware interfaces and for reconstructing logical transactions from low-level I/O signals. We demonstrate a variety of use cases for synthesizable protocol drivers and reconstructors, including runtime monitors that check security properties in the Wishbone protocol and a binding generator that synthesizes interfaces between RTL modules and programs in the Calyx intermediate language.

0.32

Peregrine: A Language-Agnostic Packet Processing Intermediate Representation with Formal Guarantees

cs.NI ·2026-10-23 ·Sean Rhee, Xiangyu Gao, Srinivas Narayana, Nate Foster, Joseph Tassarotti +1 more
code/data similarity 0.58
Abstract · 16 pages, 7 figures, 4 tables

Many different programmable network devices and domain-specific languages (DSLs) for programming them have been developed in recent years. However, the affiliated compiler infrastructure for each DSL has not kept up, leading to unreliable compilation results and ultimately a poor experience for developers. In response to this fragmented ecosystem, we propose an intermediate representation, Peregrine, to consolidate the common compiler functionalities within this domain into a shared, open-source infrastructure. We designed Peregrine to provide formal guarantees from the beginning, rather than adding them in a later step. The language comes with a formal semantics, along with an equivalence checker written and proven correct in Rocq. Experimental results show that Peregrine is general enough to express multiple applications written in various state-of-the-art network programming languages. The equivalence checker designed in Peregrine can be used for validating the correctness of a range of untrusted compiler passes, as well as for other surprising use cases such as certifying the correctness of packet classification algorithms within a reasonable amount of time.

0.38