CS Paper Radar

Specifying Paxos for System Builders: Pseudocode Made Executable

Yanhong A. Liu, Rahul Sihag

cs.DC ·submitted 2026-09-10 21:56 UTC · v1

Abstract

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.

Comment
41 pages. Extended version of invited paper at the 28th International Symposium on Stabilization, Safety, and Security of Distributed Systems. 2026

Closest papers

Nearest neighbours by meaning across the whole index.

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.64
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

Axiom: a logic programming language to express and enforce network designs

cs.NI ·2026-10-27 ·Tibor Schneider, Laurent Vanbever
similarity 0.63
Abstract

Human errors remain the leading cause of network outages. To prevent them researchers propose general verifiers that analyze the network behavior. Yet, their (symbolic) models struggle to accurately reflect network devices, they fail to scale to large networks, and report misbehavior, not what configuration line caused it. We attribute all three challenges to specifications that describe the intended behavior but not how operators intend to achieve it---the network's design: which protocols to run and how to combine them. We present Axiom, a language for expressing network designs, and a checker that finds every violation and the responsible commands. Operators state their design decision as rules over configuration commands. Axiom then compiles them into a single Datalog program that checks the entire network directly on its configurations, not on the state they produce. Our prototype checks a 754-router network within seconds. Ultimately, a design enforced on every keystroke could give network operators the integrated development environment that programmers have long enjoyed.

0.20

Certified Compilation in the TELEPERM XS Nuclear Safety I&C Platform

cs.SE ·2026-09-28 ·Alexandre Berard, Richard B. Kreckel
published similarity 0.63
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

The large safety instrumentation & control (I&C) systems in civil nuclear power plants (NPPs) are mainly safe-shutdown systems (reactor protection) or limitation and control systems. Framatome's established TELEPERM XS (TXS Core) product family is a digital I&C system platform to cover all these applications. We illustrate the role of verification in the different stages of the software production toolchain, focus on the formal compilation process, and discuss the contribution of the CompCert certified compiler to the safety case of the product. Scrutinizing the object code produced by this compiler has exhibited suboptimal run-time performance in a certain simple but recurring generated code pattern. We explain how formal methods allow us to address this issue in the compiler while simultaneously reducing its trusted computing base (TCB), thereby strengthening the safety case rather than merely preserving it.

0.33

Scenario Proofs for Verification of Distributed Protocols

cs.PL ·2026-10-11 ·Zhendong Ang, George Pîrlea, Umang Mathur
similarity 0.63
Abstract

Formal verification of distributed protocols is still dominated by inductive-invariant proofs, whose central challenge is discovering strengthening assertions that rule out unreachable states. This burden is often misaligned with how protocol designers reason: they explain correctness by following representative executions, causal histories, and phase-structured interactions among nodes. This paper introduces scenario proofs, a verification methodology that makes such execution-oriented reasoning formal. A scenario is a structured expression describing representative protocol executions, enriched with ghost variables. Rather than enumerate all possible interleavings, a scenario describes canonical executions and uses a sound semi-commutation relation to account for reorderings that preserve feasibility and final states. Verification then factors into two main obligations. Coverage shows that every feasible protocol execution is equivalent, up to semi-commutation, to one described by the scenario; this obligation is independent of the safety property and serves as a reusable behavioral characterization of the protocol. Correctness proves the desired safety property only over the representative executions, using Hoare-style weakest-precondition reasoning along the scenario structure. We formalize the scenario language, its layered semantics, and proof rules for coverage and correctness. Through case studies of ring leader election, two-phase commit, a decentralized lock, two variants of multi-signature payment, and single-decree Paxos, we show how scenario proofs capture the causal and phase-based arguments used informally by protocol designers. These examples illustrate that scenario proofs can replace monolithic invariant discovery with structured reasoning over representative executions, while retaining a rigorous connection to all feasible protocol behaviors.

0.24

Compiling Imperative Hardware Protocol Specifications to Hardware

cs.PL ·2026-11-14 ·Nikil V. Shyamsunder, Ernest Ng, Adrian Sampson, Kevin Laeufer
similarity 0.62
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.35

Stephen: Verifying Sequencer-Aided Coordination Systems with Cross-View Prophecy

cs.DC cs.PLcs.SE ·2026-11-18 ·Jinkun Geng, Muhammad Haseeb, Daniel Qian, Joseph Tassarotti, Shuai Mu +1 more
similarity 0.61
Abstract · 19 pages, 13 figures, 1 table

Many distributed systems achieve high performance by relying on dedicated sequencers to order requests, leaving replicas to commit them in that order. Despite more than a decade of such sequencer-aided coordination (SAC) systems, from Corfu and NOPaxos to LazyLog and SwitchBFT, their correctness has been argued only with pen-and-paper proofs or bounded model checking at the protocol level. In this paper, we formally verify implementations of SAC protocols. The sequencer seems to make this easy: it decides the order of all requests, so the proof can place each request's linearization point at the sequencer using a well-known technique, prophecy variables. Yet a linearization point placed at the sequencer is not durable, because the sequencer orders a request before any replica commits it. Crashes and other rare events may trigger a view change that discards the request, nullifying the earlier decision and the proof that rests on it. Our framework, Stephen, extends prophecy variables to handle view changes, and we make three contributions. (1) We develop cross-view prophecy peek, which lets the proof follow a request across view changes until it is either committed or permanently discarded. (2) Our verification uncovered bugs in existing SAC implementations, including one that can lose committed requests. We fix them and prove the fixes correct. (3) We apply Stephen to NOPaxos, Corfu and LazyLog. We build verified implementations with machine-checked proofs of linearizability. They perform within 17% of their open-source, unverified counterparts. The verified implementations and proofs will be open-sourced.

0.24

Designing a Producer-driven Stream Protocol by Formal Refinement

cs.PL ·2026-09-27 ·Erick Lavoie
similarity 0.59
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.

0.30

Validating Concurrent Correctness Witnesses with Ghosts by Thread-Modular Abstract Interpretation

cs.PL cs.SE ·2026-11-18 ·Michael Schwarz, Zhendong Ang, Umang Mathur
top venue similarity 0.59
Abstract · Accepted to POPL '27; Extended version with appendices

Concurrent programs are notoriously difficult to write and to reason about, and even tools based on sound theoretical foundations can produce incorrect results due to implementation bugs. Correctness witnesses have been proposed as a way to increase the confidence in the verdicts of software verifiers by enabling independent validation. Recently, correctness witnesses have been extended to the concurrent setting, by introducing ghost variables to allow encoding more expressive invariants. While different approaches to producing witnesses with ghosts exist, validation techniques are still lacking; instead of leveraging the information encoded in the ghosts to guide the validation process, validators merely treat ghost instrumentation and invariants over ghost variables as additional proof obligations. We propose a novel framework for the validation of concurrent correctness witnesses that exploits the semantic information encoded in ghost variables. It combines a checking phase, which establishes the semantic content of the ghost instrumentation, with an exploitation phase making use of this information. Both phases are formulated as thread-modular abstract interpretation. In particular, we consider two different classes of ghost variables and techniques for exploiting them, one based on resource invariants and one based on phases. Phase ghosts guide the degree to which the abstract interpretation considers interleavings instead of always abstracting them coarsely. In this way, the abstract interpreter can validate witnesses containing invariants beyond the reach of unguided thread-modular analysis, while still retaining its scalability benefits. We have implemented our framework in a static analyzer and evaluate it on witnesses encoding resource invariants obtained from a state-of-the-art software verifier, as well as on hand-crafted witnesses encoding phase information.

0.50