WorksComputer Science
Stephen: Verifying Sequencer-Aided Coordination Systems with Cross-View Prophecy
Abstract
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.
Introduction
I went forward in time, to view alternate futures, to see all the possible outcomes of the coming conflict.
Dr. Strange, Avengers: Infinity War (2018)
Many practical distributed systems, including databases [18, 26, 47, 53], transaction processing systems [17, 22, 38, 39, 56], shared logs [7, 21, 25, 44, 60], and distributed storage systems [27, 35, 37, 41, 59], require strong consistency in the form of linearizability. A linearizable system greatly simplifies application development by enabling developers to reason about system behavior using a simple, sequential abstraction. However, ensuring linearizability is widely acknowledged to be challenging, motivating decades of research on distributed coordination protocols. Well-studied protocols such as Paxos [31] and Viewstamped Replication (VR) [42] have undergone extensive refinement and rigorous testing in production, alleviating most concerns about their correctness.
However, canonical protocols such as Paxos and VR concentrate ordering, replication, and commitment at the replicas, and at the leader replica in particular, which becomes a bottleneck as load grows. This has motivated a line of work that offloads request ordering from replicas to independent entities, which we refer to as sequencers. Sequencers take various forms, from specialized hardware such as programmable switches to general-purpose software on end hosts. Centralizing ordering at the sequencer decouples ordering from replication and removes that bottleneck, yielding substantially higher performance. The design has therefore been adopted by a wide range of systems, including Calvin [56], Corfu [6, 7, 60], NOPaxos [39], LazyLog [44], NeoBFT [51], SwitchBFT [64] and many others [17, 38, 61]. We refer to them as sequencer-aided coordination (SAC) protocols.
The sequencer-aided design does not eliminate the complexity of coordination but shifts it to the other cases where messages are delayed, reordered, or dropped after leaving the sequencer, or where replicas or sequencers crash. Correctness therefore does not follow automatically from the common case to cover the whole protocol. Existing correctness arguments, whether pen-and-paper proofs or bounded model checking, can miss subtle bugs. Formal verification can rule out such bugs by producing machine-checked proofs of correctness for implementations of these protocols. Indeed, during our own verification effort, we uncovered bugs in several published SAC protocols (§ 4.3, § 7).
This paper presents Stephen, a general framework for formally verifying implementations of SAC protocols. To verify that these systems are linearizable, a formal proof must identify each operation’s linearization point, i.e. the moment during an operation’s execution at which it can be logically thought of as taking effect. Linearizability requires that the system’s behavior is consistent with the ordering of operations induced by the linearization points. Since determining the order of the linearization points is a key part of a linearizability proof, a natural candidate is to choose the linearization points to be at the sequencer at the moment it decides the relative ordering of an event. The replicas, by contrast, cannot play this role: in NOPaxos, for example, a request is committed once the client collects a quorum of replies, so not even the leader knows when a request commits.
While the sequencer makes it easy in a proof to decide the relative ordering of linearization points, there is an obstacle to choosing the sequencer as the linearization point in a proof. At the sequencer, the proof cannot yet determine whether a sequenced request will eventually be committed. After leaving the sequencer, requests may be delayed, reordered, or even dropped before reaching the servers. At the same time, common proof techniques require the proof to identify each linearization point at the moment it happens, as the proof steps through the code. At the sequencer, that moment arrives before the request’s fate is known: the proof must decide on the spot whether the request takes effect, yet it cannot tell whether the request will ever be committed. Prophecy variables [2], a technique supported by several verification frameworks [29, 50, 55], address exactly this obstacle. At a high level, prophecy variables allow the proof at the sequencer(s) to look ahead at the future actions taken by the servers. Based on these prophesied outcomes, the proof can derive whether a sequenced request will eventually be committed and update the abstract state accordingly. Later, when a server actually processes the request, the proof resolves the prophecy variable by recording the server’s actual action.
However, using prophecy variables directly to verify SAC systems is not straightforward, particularly in the presence of crashes and recovery. The central technical challenge arises from the decoupling between ordering and durability: one or more sequencers first assign a tentative order to requests, after which servers try to commit the requests according to that order, so a linearization point placed at the sequencer is not durable. Like VR, SAC protocols recover from crashes through a view change: the system moves to a new view and rebuilds its state from the replicas that take part in recovery. Crashes introduce additional uncertainty: if a request is sequenced but not yet committed when a crash occurs, will it eventually be committed after recovery, or will it be abandoned? An uncommitted request may either (1) survive and later be committed, or (2) be permanently discarded during recovery, and which outcome occurs depends on which replicas take part in the view change. As a result, the proof at the sequencer must make its decision in the presence of uncertainty about both future commitment and recovery behavior.
Cross-view prophecy peek. To address this, Stephen develops cross-view prophecy peek, which adopts a view-based abstraction built on top of prophecy variables that is inspired by VR [42]. Cross-view prophecy peek records a separate prophesied value for each view, which confines the non-determinism of crash recovery to one view at a time. Consider an uncommitted request whose fate is uncertain in the current view. Cross-view prophecy peek allows the proof to look ahead at the request’s assigned slot across subsequent views until it finds a view in which the request is either committed by a majority of servers or permanently replaced by a no-op. This enables the proof at the sequencer to soundly determine the outcome for the linearizability argument.
Identifying bugs and escrow technique. Prophecy variables also impose an additional discipline on the proof. In several verification frameworks, prophecy variables have an associated notion of permission or ownership, which is required to resolve a prophecy variable, i.e. to attach the prophesied value to the program event it is designed to make predictions about. Just as Rust’s ownership system rules out certain forms of races, this ownership discipline for prophecies is needed to make it clear which event is being predicted [29]. While verifying several SAC implementations with our technique, we realized that this ownership discipline was being violated in our initial proof attempts, which uncovered bugs in the actual implementations. For example, in NOPaxos, a replica that crashes may rejoin the same view after a state transfer and reprocess slots it had already processed. In our proof, this would have required changing which value the prophecy’s prediction was about, which these ownership rules forbid. This is not merely a proof technicality. It corresponds to a concrete bug in which the client is told that a request is committed, yet the request is lost during recovery. Similar issues exist in other SAC protocols (e.g., Eris [38], Hydra [17]). To fix it, we adopt the escrow technique [49, 57]: when restarting, each replica draws a fresh, non-duplicable token at boot, and the coordinator releases a view’s resolution permission to the replica in exchange for the one token. A replica that crashes and reboots holds a different token, so it cannot reclaim that permission to resolve prophesied values in that view.
Our contributions. We implement Stephen in Grove [50] and demonstrate it on three representative SAC systems: NOPaxos, Corfu and LazyLog. Stephen makes three contributions:
(1) Stephen introduces cross-view prophecy peek, a novel verification technique that is generally applicable to SAC systems. It resolves the fundamental uncertainty arising from the decoupling of ordering and durability under crash recovery.
(2) Stephen exposes multiple bugs in existing SAC protocol implementations. The most consequential one surfaced through the prophecy discipline: a replica that rejoins its previous view resolves a prophecy twice and loses a committed request. We develop our remedy based on the escrow technique and prove the fix is correct.
(3) Stephen delivers machine-checked proofs and verified implementations of NOPaxos, Corfu and LazyLog. Our evaluation shows that the verified implementations perform comparably to their open-source, unverified counterparts (within 17%).
Overview of SAC Protocols
In this section, we provide background on SAC protocols by describing their common design pattern and highlighting where individual protocols diverge.
In traditional coordination protocols like Paxos and VR, the leader replica is responsible for ordering, replicating, and committing requests, leading to a performance bottleneck. SAC protocols avoid this by decoupling ordering from replication: one or more dedicated sequencers establish a tentative order for incoming requests ahead of replication, while replicas focus solely on processing and committing requests in that order. In the common case, replicas simply follow the sequencer-determined order, making the sequencer(s) the effective linearization point.
However, the tentative order may not always hold. Requests can be delayed, reordered, or dropped after leaving the sequencer, and replicas or sequencers may crash. SAC protocols therefore incorporate additional mechanisms to handle these abnormal cases while preserving linearizability.
We illustrate this common structure and key design differences using three typical protocols: NOPaxos [39], Corfu [7], and LazyLog [44]. Figure 1 shows their workflows.
Figure 1. Workflows of three representative SAC protocols.
_Sequencing and ordering._ In all three protocols, the sequencer assigns each request a monotonically increasing sequence number that determines the tentative ordering. The protocols differ in how requests reach replicas after sequencing. In NOPaxos, the sequencer directly multicasts each request to all replicas. In Corfu, the sequencer returns the sequence number to the client, which then delivers the request to replicas in a client-driven chain-replication style. LazyLog employs multiple sequencers; clients multicast request metadata to all sequencers and send request data directly to all replicas. Among the sequencers, one is designated as the leader and determines the linearizable order. (We refer to LazyLog’s Erwin-st variant [44] with a single shard.)
_Commitment._ In the common case, replicas process requests in sequence-number order and send replies to clients. NOPaxos commits once the client collects replies from a quorum of replicas. Corfu commits a request once all replicas in the chain acknowledge it. LazyLog commits once the client receives replies from all sequencers and all replicas.
_Inconsistency handling._ When requests are delayed, reordered, or dropped after sequencing, replicas may not observe the tentative order, and each protocol resolves the resulting inconsistencies differently. In NOPaxos, the leader replica runs gap agreement, contacting a quorum to mark the missing slot NOOP so that replicas can move on. In Corfu, later requests fill the missing slots with lazy values, which can freeze into NOOPs by chain replication, so that a late request can no longer occupy the slot even if it eventually arrives. In LazyLog, the leader sequencer reconciles the order in the background: once replicas agree, it advances a local counter (last-ordered-gp), then synchronizes across sequencers and advances a second one (stable-gp; see §4.3 of [44]).
_Crash recovery._ When replicas or sequencers fail, each protocol uses a different recovery mechanism. NOPaxos uses a VR-style view change to elect a new leader and recover committed requests. During recovery, uncommitted requests may either be committed or abandoned, depending on which replicas participate. Corfu employs a reconfiguration protocol based on Vertical Paxos [32] to recover committed requests and replace failed components. LazyLog elects a new leader sequencer and initiates a view-based recovery procedure. The new leader flushes its log to the replicas, potentially overwriting the order established by the previous leader while preserving linearizability.
This non-determinism during crash recovery significantly complicates correctness reasoning. Uncommitted requests may survive or be permanently discarded depending on the recovery outcome, yet the proof must account for all possibilities at the time of sequencing. We discuss how Stephen addresses this challenge in § 3.
Verification with Prophecy Variables
This section provides an overview for prophecy variables [29], and explains how prophecy variables can support the proof that depends on future events. However, we will continue to show, simply adopting the conventional prophecy variable design is insufficient to handle the non-determinism when verifying SAC systems with crash recovery, which motivates our design of cross-view prophecy peek (§ 4).
Overview of Prophecy Variables
Many program verification techniques proceed line-by-line through programs, reasoning about how the system’s state would evolve as each statement of the program is executed. A prophecy variable allows us to know, during the proof, what the eventual value of a program expression will be before getting to the place where that expression executes.
As a simple example adapted from [29], consider a lazy coin. Figure 2 shows two implementations. An eager coin (left) flips immediately at creation time and stores the result. A lazy coin (right) defers the flip: new_coin() creates the coin with value None, and the actual flip only happens on the first call to read_coin(). From a client’s perspective, the two are indistinguishable, so they should have the same specification: after creation, there exists some boolean such that every read returns .
Figure 2. Eager and lazy coin implementations (adapted from [29]). Gray lines are ghost code that exists only in the proof. NewProph creates a prophecy variable with an existentially quantified value. Resolve records the actual outcome. The predicate connects the prophecy variable to the postcondition.
The verification challenge arises when proving new_coin() for the lazy implementation. The postcondition must state that the coin has some value , but will not be determined until the first read_coin() call. The proof cannot instantiate at creation time, so it gets stuck. A prophecy variable resolves this (line 3, right): at new_coin(), the proof introduces a prophecy variable to represent the future flip result. The postcondition can now be stated in terms of this prophesied value. Later, when read_coin() performs the actual flip (line 10, right), the prophecy is resolved: the prophesied value must equal the concrete flip result in order for the proof to complete.
These prophecy variables are just ghost code annotations that are used for tracking information in the proof. They are erased during compilation and have no effect on the program’s actual behavior at run time.
Prophecy Variables for SAC Protocols
To prove linearizability for SAC protocols, Stephen maintains a ghost log that records the abstract sequential history of committed requests. Each time the sequencer assigns a sequence number to a request, the proof must decide whether to append the request to this ghost log. If the request will eventually be committed by the replicas, it should be appended; if the request will ultimately be uncommitted (e.g., dropped), it should not. This decision must be made when the sequencer assigns the sequence number, because the sequencer is the linearization point where the request’s position in the ghost log is determined.
The difficulty is that when the sequencer assigns the sequence number, the request has not yet reached the replicas. The request may arrive in order and form a quorum, or it may be delayed, reordered, or dropped. Replica crashes add further uncertainty. Without prophecy variables, the proof at the sequencer step has no direct way to refer to the replicas’ future actions, and thus cannot determine whether to extend the ghost log.
To address this, for each replica and each request slot, Stephen introduces a prophecy variable for the replica’s future action for that request: either Normal (place the request at this slot) or NOOP (mark the slot as a no-op operation). This lets the proof reason in two stages. At the sequencer step, the proof examines (peeks at) the prophecy variables across replicas. Since these variables reflect the replicas’ eventual actions in the current execution, the proof can determine whether the request will be committed and decide accordingly whether to extend the ghost log. At the replica step, the proof resolves the prophecy variable by recording the replica’s actual action. Since the prophesied value reflects what actually happens in each execution, the two always agree.
For example, consider NOPaxos. After the sequencer multicasts a request to replicas, the request is committed only if it arrives at a majority of replicas (including the leader) in the sequencer-assigned order. However, a subsequent request with a larger sequence number may arrive at replicas earlier, while the current request is delayed or dropped. In such a scenario, the NOPaxos leader initiates gap agreement, contacting a majority of replicas to mark the missing slot as NOOP. Once complete, the original request can no longer be committed at that slot. These two outcomes (commit vs. no-op) correspond to different execution traces, each with different prophesied values in the replicas’ prophecy variables. Similar non-determinism arises in other SAC protocols such as Corfu, where later requests fill gaps with junk values.
Derivation with Prophecy Variables
We now illustrate the prophecy variable design in more detail using NOPaxos as an example. Every Replica- owns a sequence prophecy variable [29], i.e., a list of prophesied values (pvs) that describe the replica’s future behavior. Let
denote Replica-’s prophecy list; the th element is either Normal (request arrives and is appended) or NOOP (request is dropped and the slot is marked via gap agreement). The sequencer peeks at these values across all replicas to derive each request’s fate. Figure 3 illustrates this with replicas (), where Replica-0 is the leader. We walk through three requests.
Figure 3. Prophecy variable design for NOPaxos. Each row represents the prophecy list of one replica, which contains the prophesied replica action for each request. Replica-0 is the leader replica. This single-view design cannot resolve ambiguity introduced by crash recovery (see Request-2).
Request-0 (committed). The leader (Replica-0) and at least followers (Replica-1, Replica-2) have Normal. Since a majority including the leader will append the request, the proof concludes that Request-0 will be committed and extends the ghost log with a Normal entry.
Request-1 (no-op). The leader’s prophecy list indicates NOOP. This corresponds to an execution where the leader does not receive Request-1 and completes gap agreement for that slot. Regardless of what the followers do (i.e., either they receive Request-1 or not), the slot for Request-1 becomes a no-op. Correspondingly, the proof extends ghost log with a NOOP entry instead of a Normal entry.
Request-2 (ambiguous). Replica-0’s prophecy list has no entry for Request-2, because Replica-0 crashes before resolving it. Request-2 arrives at Replica-1, Replica-3, and Replica-4 (all record Normal), but is dropped at Replica-0 and Replica-2. Before crashing, Replica-0 initiates gap agreement; Replica-2 receives the leader’s gap instruction and marks the slot as NOOP. At this point, the prophecy lists do not contain enough information to determine Request-2’s fate: depending on which replicas participate in crash recovery, the request may be either committed or discarded. This ambiguity cannot be resolved with the current single-view prophecy design, motivating the cross-view extension in §4.2.
Cross-View Prophecy Peek
The previous section showed how prophecy variables enable the proof to derive request outcomes, but also revealed that the single-view design cannot resolve ambiguity when replicas crash (Request-2 in §3). Crash recovery introduces further non-determinism: the same request may be committed or discarded depending on which replicas participate in recovery. This section presents cross-view prophecy peek, our key technique for reasoning about SAC protocols under crash recovery. We also describe the bugs we discovered in existing protocols and the escrow-based fix.
Non-Determinism in Crash Recovery
We continue with the NOPaxos example from §3. In Figure 3, after the leader Replica-0 crashes, the remaining replicas elect a new leader, which contacts replicas (to form a majority) to recover the log. The recovery procedure guarantees that all previously committed requests (e.g., Request-0) are recovered and that all slots that were previously agreed as gaps remain gaps (e.g., Request-1). For requests that were neither successfully committed nor conclusively marked as gaps before the crash (e.g., Request-2), the recovery outcome is non-deterministic; it depends on which replicas participate in the recovery and what messages they receive first.
Consider Request-2 as an example. Suppose Replica-1 is elected as the new leader. If Replica-1 contacts Replica-3 and Replica-4 during recovery, then all replicas in the recovery quorum record Request-2 as a normal entry, and Request-2 is eventually committed. In contrast, if Replica-1 contacts Replica-2 and Replica-3, then Replica-1 observes a NOOP entry in Replica-2’s log. Following NOPaxos’s recovery rules (§5.2.3 in the NOPaxos paper [39]), Replica-1 will mark Request-2 to be NOOP in the recovered log. Thus, the same request may either be committed or discarded depending solely on the recovery quorum.
Similar non-determinism arises for subsequent requests. For example, Request-3 is multicast by the sequencer but arrives only at Replica-4 and is dropped by the other replicas. If Replica-4 participates in recovery, then Request-3 may be recovered and eventually committed. If Replica-4 does not participate, then Request-3 does not appear in the recovered log at all. In such executions, after the sequencer multicasts Request-4, it should not make any update to the ghost log for Request-3, since the request is never committed.
These examples illustrate that crash recovery introduces non-determinism that the single-view prophecy design from §3 cannot handle. The challenge is not simply that the future is unknown, as in the case without recovery. Rather, crash recovery makes the future non-deterministic: for the same request, different recovery quorums yield different outcomes. A single prophesied value per replica per request cannot capture this, because replicas may take different actions across different views. To address this, we extend the prophecy variable design to track replica actions per view, enabling the proof to follow a request’s fate across view changes.
Cross-View Prophecy Peek Design
Our design is inspired by the view-based mechanism in Viewstamped Replication [48], where views provide a clear boundary for handling crash recovery. After each recovery, replicas with restored state (i.e., logs) transition into a new view.
For each request, Stephen does not model replica behavior using a single prophesied value. Instead, it adopts a finer-grained, view-aware design. Concretely, for each replica, Stephen constructs a two-dimensional prophecy list, where denotes the Replica-r’s action for Request-j in view . Since these prophecy lists reside in the global invariant and are accessible to the sequencer, the sequencer can peek at multiple prophesied outcomes for each request, enabling it to infer the eventual outcome of multicast requests. Figure 4 illustrates the same four requests as in Figure 3, now extended across two views ( and ).
Figure 4. Cross-view prophecy variable design for NOPaxos. For simplicity, here we only consider view change and ignore session change (i.e., triggered by sequencer’s crash recovery). Replica-0 is the leader in the old view , after it crashes, Replica-1 becomes the new leader. Replica-1, Replica-2 and Replica-3 establish the recovery quorum and recover the system state, so the recovered state for the four requests is reflected in the prophecy variables in higher view .
For Request-0 and Request-1, the sequencer can determine their eventual outcomes by inspecting the prophesied values in view . However, for Request-2 and Request-3, Replica-0 (the leader in ) no longer provides sufficient information, preventing the sequencer from conclusively determining their outcomes. Unlike the setting in Figure 3, the finer-grained design allows the sequencer to continue peeking into the next view (), where Replica-1 is the leader and forms a recovery quorum with Replica-2 and Replica-3. Based on the prophesied values in , Request-2 is recovered as a NOOP, while Request-3 is discarded (since Replica-4 does not participate in recovery). Therefore, the sequencer can safely update the ghost log: it appends a NOOP entry for Request-2 and leaves the log unchanged for Request-3.
Cross-view prophecy peek generalizes to multiple consecutive crashes. If Replica-1 also crashes, the sequencer continues peeking into future views () until it can determine each request’s outcome. The approach also handles sequencer crash recovery. In NOPaxos, the view identifier is a pair , where is incremented on sequencer recovery. Cross-view prophecy peek operates over both dimensions, allowing the proof to reason about requests across sequencer and replica failures (see § 5).
At-Most-Once Prophecy Resolution
While the sequencer peeks at prophecy variables to derive request outcomes, each prophesied value (pv) must eventually be resolved when the replica processes the request.
Upon receiving a request, the replica either appends it as a Normal entry or marks its slot as NOOP. In the proof, this step resolves the corresponding prophesied value in . A prophecy variable is an exclusive resource in separation logic: only its owner may resolve it, and each resolution consumes the prophesied value at the head of [29]. Consequently, each prophesied value can be resolved at most once, and only by the replica that owns .
Based on this at-most-once requirement of prophecy resolution, we revisit the crash recovery procedures in open-source SAC implementations. Among the systems we examined, few implement crash recovery at all, which is anecdotal evidence that recovery is a difficult and error-prone part of the design. For those that do include recovery (e.g., NOPaxos [40]), we find that they do not guarantee at-most-once resolution for every prophesied value. Specifically, in NOPaxos, a failed replica may rejoin the system in the same view as before the crash. Because NOPaxos is an in-memory protocol without durable storage, the rejoined replica does not retain its prior behavior, even if it has already resolved prophecies in that view. As a result, the proof would have to resolve the same prophesied value a second time. The exclusivity of forbids this, so the linearizability proof cannot be completed.
A failed proof attempt does not by itself imply a bug in the protocol. However, in this case, we observe that there is an underlying concrete correctness bug in NOPaxos, as we show below with an explicit buggy trace.
Error trace in physical execution. We consider Replica-0 as the leader in view . Before crashing, Replica-r () receives all requests, appends them as normal entries, and sends replies to clients. Suppose the last request, Request-j, arrives at Replica-r first. The remaining replicas have not yet received Request- when Replica- crashes and initiates recovery. During recovery, Replica- contacts other replicas, but since none of them have received Request-, it only recovers Request-0 through Request-.
We then let each follower replica follow the same crash-recovery pattern, such that each sends a reply for Request- before crashing, but fails to recover it afterward. Eventually, Request- reaches Replica-0 (the leader), which also replies in view before crashing. At this point, the client has collected sufficient replies to satisfy the quorum condition and thus considers Request- committed. However, after the leader crashes, none of the remaining replicas retain Request-. As a result, although the client observes Request- as committed, the request is permanently lost.
Escrow Technique
To prevent duplicate resolution, we adopt the escrow technique [49, 57], which enables exclusive resources to be conveyed through duplicable assertions while ensuring that they can be extracted at most once.
The root cause of the bug is the lack of permission control over prophecy resolution within each view. A crashed replica can rejoin and re-resolve prophecies it already resolved. A natural fix is to require replicas to obtain a one-time permission before resolving. In practice, SAC systems already rely on a fault-tolerant coordinator (e.g., ZooKeeper [4]) to manage control-plane metadata, so we use this coordinator to manage resolution permissions as well. We assume the coordinator is correct and place it outside the scope of our verification. Verified implementations of such coordinators are also available, e.g., Grove [50] provides a verified Paxos-based coordinator.
The escrow pattern enforces one-shot permission transfer using two components: a duplicable invariant and an exclusive token. When Replica- starts or reboots, it creates a globally unique identifier , which grants it an exclusive token in the proof. The coordinator creates an escrow invariant that links the resolution permission to this token:
To obtain , Replica- surrenders its token to the escrow invariant in exchange for the permission. Since is exclusive (i.e., ), this exchange can happen at most once.
If Replica- crashes, it loses . Upon reboot, although the coordinator may re-transfer the same invariant , Replica- cannot regenerate the same identifier and thus does not possess the corresponding token . Consequently, it cannot reclaim and is prevented from resolving prophecies again in the same view .
On the coordinator side, correctness requires that each is linked to at most one token. The coordinator enforces this by recording issued identifiers and allocating fresh view identifiers for new permissions. When it receives a fresh identifier, it creates a new escrow invariant; otherwise, it re-transfers the existing one.
Instantiating the Proof
This section describes the concrete instantiation of Stephen following the order of the abstract state, prophecy resolution and prophecy peek. We take NOPaxos, Corfu and LazyLog as examples to illustrate how we instantiate proof. However, Stephen is generally applicable to other SAC systems.
Abstract State
Each system represents its abstract state as a ghost log: an ordered list of entries that lives in the global invariant and is updated atomically by the sequencer alone. Every Replica- owns a sequence prophecy variable , which is a list of prophesied values (pvs) that describe the replica’s future behavior. Because the prophecy variables also live in the global invariant, the sequencer can peek at all of them, across views. Each time a request passes through the sequencer, the sequencer-side proof peeks at the prophecy variables and performs one atomic update to the ghost log: it decides whether to append a Normal entry, append a NOOP entry, or leave the ghost log unchanged.
Prophecy Variable Design
In general, there are two aspects of a replica’s behavior that matter for the proof: the boundaries of its lifecycle, which alternates between view changes and normal processing, and the actions it takes on individual requests during normal processing. Each sequence prophecy variable therefore contains two categories of pvs:
(1) Marker pv , which marks a lifecycle boundary of the replica across views.
(2) Entry pv , which records the action taken in view on the request (identified by ) placed at log position .
We now explain the fields common to all protocols. Notably, a resolved pv can also carry protocol-specific information, which we omit here.
In NOPaxos, the view is a pair , where increments when the sequencer crashes and increments when the leader replica fails. In Corfu, a Paxos-based coordinator manages views, so is a single configuration epoch. is the set of replicas that participate in view . It is constant in NOPaxos, whereas Corfu relies on the coordinator to reconfigure the replica set for every view, so entry pvs from different views can carry different .
A marker pv is resolved at one of three lifecycle events: StartViewChange, when the replica starts a view change; CompleteRecovery, when it has recovered the log entries of previous views; and StartNormal, when it begins normal processing in the new view. records the log position at which the new view’s normal processing begins. An entry pv is resolved whenever a replica handles a request during normal processing. The request identifier and the value domain of are protocol-specific.
NOPaxos. A request is identified by : the session in which the sequencer multicast it and the sequence number it received. Both fields are needed because the sequencer resets in every new session. Note that may be lower than when a request multicast in one session is committed only after the sequencer has been replaced. The is Normal or NOOP. A prophecy variable may contain two entry pvs for the same log position that differ only in , e.g., Normal when the request arrives and is placed at , and NOOP when the leader later runs gap agreement for that slot .
Corfu. A request is identified by , where is the view in which it was sequenced. Corfu’s sequencer assigns globally increasing sequence numbers that are not reset across views, so a request’s log position equals its sequence number. The is Normal, Junk, or NOOP, where Junk marks a slot that a replica filled provisionally when a request with larger arrives first. But junk value can be later replaced by the request or finalized as a no-op, which also causes the replica’s prophecy variable to hold two entry pvs for the same log position but with different actions.
LazyLog. Unlike in NOPaxos and Corfu, a sequencer-assigned does not uniquely identify a request in LazyLog, because a new leader sequencer may overwrite the order established by its predecessor. Stephen instead uses , where is a per-client counter and is a fresh identifier that Stephen generates for the client on every reboot. Together with , they identify a request uniquely across client reboots. The is Normal or NOOP. LazyLog’s sequencers also replicate requests, so each sequencer owns a prophecy variable as well. A sequencer replicates only metadata and always resolves Normal, whereas a replica resolves NOOP for a position whose payload never arrives.
Prophecy Resolution
Prophecy resolution takes place at the replicas. A resolution records an execution outcome at a replica that the sequencer cannot know when it multicasts the request. But the sequencer-side proof can peek at these pvs to decide how to extend the ghost log. This subsection describes resolution at the replicas; § 5.4 describes the prophecy peek.
In all SAC systems verified by Stephen, Replica- must acquire from the coordinator through the escrow pattern (§ 4.4) before it resolves any pv in view . It then follows a common two-phase pattern: (1) it resolves entry pvs for the log entries recovered from previous views, and (2) it resolves entry pvs for new requests as it processes them. Marker pvs delimit these phases. The protocols differ in how requests reach the replicas and in which actions an entry pv may record.
Marker pv resolution and interaction with coordinator. Marker pvs are resolved during a replica’s interaction with the coordinator. The coordinator is built on a conventional consensus protocol such as Paxos or Raft and recovers from crashes on its own. Its internals are outside the verification scope of Stephen, and Grove’s verified Paxos could serve as an implementation. The interaction between the coordinator and the replicas/secondaries, however, is pivotal to the correctness of SAC protocols, and Stephen verifies it.
The coordinator records the current view and the replicas and sequencers active in it. Replicas and sequencers interact with it through three RPCs.
CheckRPC. Replicas and sequencers periodically call CheckRPC on the coordinator. It doubles as a heartbeat: if a server falls silent past a timeout and its failure halts service, the coordinator increments the view identifier. The reply carries the coordinator’s current view; a server that sees a higher view than its own starts a view change. Before Replica- starts the view change toward view , it resolves a marker pv from with and .
PermissionRPC. After the view change, a replica must not resolve entry pvs for its recovered log right away, because of the risk of duplicate resolution (§ 4.3, § 4.4). It first obtains from the coordinator through PermissionRPC, which implements the escrow pattern. Holding the permission, Replica- resolves an entry pv for every recovered entry in view , then a marker pv with and , and reports its progress to the coordinator through StabilizeRPC.
StabilizeRPC. Once enough replicas and sequencers have reported ready, the coordinator tells them to resume service in view . On that notification, Replica- resolves a marker pv with , , and set to the log position of the view’s first new request, then resumes normal processing.
During normal processing, Replica- resolves one or more entry pvs from for every request it processes. The details depend on the protocol, as described below.
NOPaxos. When arrives and matches the next expected slot, Replica- appends it at log position and resolves an entry pv from :
If the leader later runs gap agreement for that position, Replica- resolves a second entry pv from that agrees with on , , and but has .
Corfu. When arrives at Replica-, the replica first checks the log positions below . For every position that is still empty, it fills with a junk value and resolves an entry pv from :
It then places req at its own position and resolves the pv e:
Both resolutions record rids, i.e., the replicas that form the chain in view v. Since the coordinator may reconfigure the chain at every view change, the sequencer-side proof needs e.rids to know whose prophecy variables to examine (§ 5.4). Moreover, because Corfu never resets sequence numbers after a sequencer crash (NOPaxos does), a request’s log position is simply its sequence number, e.pos = req.id.seqNo.
A filled junk value is later replaced either (1) by a Normal entry, if the missing request eventually arrives, or (2) by a NOOP entry, if the leader (head) replica synchronizes with the other replicas and freezes the position against late arrivals. Each replacement resolves a further entry pv with the new action, so the entry pvs capture both execution traces, from Junk to Normal and from Junk to NOOP.
LazyLog. In LazyLog (Erwin-st), both sequencers and replicas resolve entry pvs, since both replicate request data: sequencers the metadata, replicas the payload. When req arrives at a sequencer in view v, the sequencer appends it at its local position localPos and resolves an entry pv e:
Different sequencers may place req at different local positions. During LazyLog’s background ordering, the leader sequencer agrees with the follower sequencers and the replicas on a single position globalPos for req, and each of them resolves an extra entry pv with e.pos = globalPos.
Sequencers hold no payload, so their entry pvs always carry e.action = Normal. A replica, in contrast, may discover during background ordering that it never received req’s payload. As in NOPaxos, the leader replica then reaches gap agreement with the followers, and the replicas resolve the entry pv with e.action = NOOP.
Prophecy Peek
When the sequencer processes a request, the sequencer-side proof peeks at the prophecy variables of all replicas, across views, to determine whether the request will be committed. Each protocol has its own commitment condition; the differences lie in the quorum requirement and in protocol-specific constraints. Here we explain NOPaxos’ peek process in detail and describe Corfu’s and LazyLog’s peek in appendix(§A–B).
NOPaxos. When req passes through the sequencer, the sequencer tags it with req.id = (sessionId, seqNo). The sequencer-side proof decides whether req will eventually be committed, and further decides whether it can extend the ghost log. We formalize this behavior as the logically atomic Hoare triple [29] in Figure 5. The angle brackets <<< >>> delimit the atomic update at linearization point: the handler either appends an entry to ghost log or leaves it unchanged. To make the decision, the proof distinguishes two cases.

Figure 5. The logically atomic Hoare triple for the NOPaxos sequencer’s message handler.
Case 1: req is committed during normal processing. After the sequencer multicasts req, the request is committed without any intervening sequencer or replica failure, that is, without a view change. The commit condition is
We explain in more detail. The sequencer-side proof performs a two-step check during the peek.
(1) A leader-inclusive quorum of f + 1 replicas has started normal processing in some view, so their prophecy variables all contain the same marker pv m with m.event = StartNormal. We define this check as qsMarker(Q, m, ev), and a leader-inclusive quorum Q that supports a pv p as qsSupport(Q, p), so qsSupport(Q, m) implies that a quorum of replicas have started normal processing in the view m.v.
(2) Given the candidate view e.v, the proof checks whether the pvs provide sufficient evidence that req is committed: a leader-inclusive quorum of replicas must hold an entry pv e for req in this view. Besides, req can commit only after every request multicast before it in the same session has been committed in sequence-number order. The proof therefore also checks that the replicas’ prophecy variables support both req and req’s prefix, defined as qsPrefix(e):
Case 2: req is committed during recovery. Alternatively, req is not committed right after the multicast: the sequencer or a replica crashes and triggers a view change, so sessionId or viewId is incremented. After the view change, req is included in the recovered log and replicated to a leader-inclusive quorum, which also commits it. The commit condition is
The proof considers committed if replicas’ prophecy variables provide sufficient evidence for either case:
A committed lets the sequencer-side proof atomically extend the ghost log with an entry, depending on in the commit condition that satisfies. If the quorum of replicas agree on , the ghost log is appended with a Normal entry, meaning that is committed with its payload. Otherwise, it is appended with a NOOP entry, meaning that ’s log position is finally marked as a no-op.
If no such evidence exists, is never committed in this execution, and the ghost log remains unchanged.
Corfu. The peek for Corfu follows the same shape as for NOPaxos: the sequencer-side proof checks whether commits during normal processing or during recovery. There are two major differences. (1) Corfu commits a request only when every replica in the chain acknowledges it, so the proof must find an entry for in every replica’s prophecy variable, not just a majority. (2) Corfu is a shared log, and an append is acknowledged without executing the entries before it, so the normal-processing condition does not require the replicas’ prophecy variables to agree on the prefix of earlier requests. Appendix § 12 explains more details.
LazyLog. The peek for LazyLog follows the same shape as for Corfu, with two major differences. (1) LazyLog’s sequencers replicate request metadata, so the full quorum that the proof examines includes every sequencer as well as every replica. (2) The leader sequencer decides only a tentative order: may commit at the log position that the leader assigns, or at a different position that a new leader decides after a view change. The proof therefore also checks the leader’s scope. It peeks at the subsequent marker to learn the last log position committed by the current leader. If goes beyond this scope, extending the ghost log for is the responsibility of a later leader, not the current one. Otherwise, the proof follows conditions similar to Corfu’s to decide whether is committed and, if so, whether it is committed as Normal or NOOP. Appendix § 13 explains more details.
Implementing Verified SAC Systems
Codebase. To implement the verified versions of SAC systems, we take the open-source implementations of NOPaxos [40], Corfu [43] and LazyLog [45] as reference and port them to Go, and translate the Go code into Rocq specifications with Goose [11]. Based on the specification, we develop machine-checked proofs on top of them in Grove [49, 50]. The open-source code is incomplete with respect to failure handling: NOPaxos implements view change but not replica rejoin; Corfu and LazyLog implement neither view change nor most of the crash-recovery logic. For the missing parts we follow the protocol descriptions in the respective papers. Verification then iterates: when a proof attempt exposes a bug, we revise the implementation, translate it again, and resume the proof, until the implementation is fully verified. Coding agents such as Codex and Claude provide some assistance to develop the proof, but the key proof insights still require human expertise to audit, revise, and supply. Table 1 summarizes the size of each codebase.
| Protocol | Open-Source Code | Verified Code | Rocq Spec | Rocq Proof | Proof/Source Ratio |
| NOPaxos | 4,914 | 8,442 | 7,810 | 175,808 | 20.8× |
| Corfu | 2,365 | 5,830 | 5,847 | 86,305 | 14.8× |
| LazyLog | 3,552 | 7,363 | 7,856 | 183,239 | 24.9× |
Table 1. Code size (lines of code) of SAC protocols
Trusted code and axioms. Our verification relies on several trusted assumptions, which appear as axioms in the proofs. (1) We assume that network communication is implemented correctly, so we reuse the network axioms built into Grove and focus on the protocol logic. (2) We assume that universally unique identifiers can be generated [46]. Our implementation obtains them through a trusted API, getUUID, and one corresponding axiom supports both the proof of the escrow pattern (§ 4.4) and the fix for the client-reboot bug we found in both protocols (§ 7). (3) The coordinator’s crash recovery is outside the scope of Stephen, and Grove already provides a verified Paxos module that could serve this role.
Public APIs and verified spec. Each SAC protocol exposes two public APIs in Figure 6, and each API carries the logically atomic Hoare triple in Figure 7 that specifies its behavior and is verified in Grove. When a write succeeds, the ghost log holds the corresponding entry at some position , and the reply carries that position. The postcondition also hands the client a witness that the entry is recorded there, which the client can later pass to the read API. A successful read returns that entry, with a witness that it is the one the ghost log holds at that position.

Figure 6. Stephen public APIs.

Figure 7. Logically atomic Hoare triples for Stephen’s client APIs. We omit several conjuncts for readability.
Other Bugs and Lessons
Besides the duplicate-resolution bug in § 4.3, our verification with Stephen uncovered several other bugs. The first two are safety bugs. In both cases the proof could not be completed, and the failed proof obligation led us to the bug. The third is a liveness bug in our own implementation, which the proof cannot detect and which we found during testbed evaluation.
Client reboot. The open-source implementations of all the three protocols mishandle client reboots. A client maintains an in-memory counter to uniquely identify the requests it submits. The counter is volatile and its value is lost when the client crashes. After rebooting, the client may reuse a for a different request. If a reply to the earlier request is delayed in the network and arrives after the reboot, the client mistakes it for a reply to the new request and wrongly considers that request committed. Our fix is inspired by crash vectors [46]: on every reboot, the client generates a fresh universally unique identifier (UUID) and attaches it to each request alongside . The pair names a request uniquely across reboots, and replicas echo both in their replies (Figure 7), so the client can tell stale replies apart from replies to its current request.
Premature truncation of logs. The second safety bug lies in NOPaxos’s view change. In NOPaxos’s open-source implementation [40], the replica attempts to truncate its log prematurely during view change. When its last normal view is below the reconstruction pivot in START-VIEW, the replica rewinds to its local commit point before fetching the replacement suffix. This rewinding can target already executed entries even when the existing log agrees with the recovered log. Because rollback is unimplemented, the replica aborts instead of completing recovery. We identified an execution with five replicas and two external crashes in which this premature rewind aborts a third replica, leaving fewer than a quorum alive and preventing progress even after communication recovers. Our fix defers truncation until the suffix arrives and the combined log is validated against the START-VIEW summary, so an interrupted transfer always leaves an intact log. Since the bug lives entirely in this truncation optimization, model checking the high-level protocol spec cannot find it.
Liveness bug. We also encountered a liveness bug in our verified implementation of NOPaxos. Stephen verifies safety only, so the proof checker cannot detect such bugs, and we found this one during testbed evaluation. The bug arises when the leader replica instructs followers to start a new view. A follower whose log is inconsistent with the leader’s log issues a state transfer request to fetch the missing entries. Our implementation imposed an overly strict validity check on these requests and rejected all of them. The followers therefore never obtain the missing entries and remain in view-change state, while the leader never collects enough responses to enter the new view. The system stops making progress. Because the bug does not affect safety, its proof still passed the proof checker. We fixed the bug and re-ran the proof checker against the corrected code. This bug illustrates a limitation of Stephen: it proves linearizability but not liveness, so testing remains necessary to catch progress bugs.
Evaluation
We evaluate the performance of our verified implementations against their open-source, unverified counterparts. All experiments run on Google Cloud, using n1-standard-4 VMs for clients and n1-standard-16 VMs for sequencers, replicas, and coordinators. The open-source implementation of Corfu [43] and LazyLog [45] communicates over RDMA, which is not supported by Google Cloud. For a fair comparison, we replace their communication library, eRPC [30], with rpclib [52], so that the verified and unverified versions both communicate over TCP. We refer to our verified implementations as NOPaxos-v, Corfu-v, LazyLog-v, respectively. For each test case, we run 5 trials and report the median value among them.
NOPaxos-v. We deploy NOPaxos and NOPaxos-v with 3 replicas each. Figure 8 shows their throughput and median latency during normal processing as we keep adding closed-loop clients. NOPaxos-v performs comparably to NOPaxos, with a gap within 15%. Figure 9 shows NOPaxos-v under a crash and recovery. We fix the load at 20 clients, which brings NOPaxos-v close to saturation, and kill the leader at s. Successful client requests resume about 5 seconds after the crash. At s, we restart the failed replica. It rejoins as a follower, which triggers another view change, and client requests resume about 1.4 seconds after restart. This recovery time is comparable to the numbers reported from state-of-the-art consensus protocols in public cloud [22, 23].
Figure 8. NOPaxos vs. NOPaxos-v
Figure 9. NOPaxos-v crash recovery
Corfu-v. We deploy Corfu and Corfu-v with a chain of 3 replicas and compare them under two workloads: appends only (Figure 10a), and appends and reads issued concurrently (Figure 10b). Every append carries a 4KB payload. Under the append-only workload, we increase the client number from 1 to 60. Corfu-v adds 2.0%–14.7% to append latency and gives up 3.9%–16.9% of throughput.

Figure 10. Corfu vs. Corfu-v
In the mixed workload, each client runs a writer thread and a reader thread. The writer appends at a fixed rate of 1K ops/s and the reader repeatedly reads the latest entry its writer has committed, so 15, 30, and 60 clients drive append rates of 15, 30, and 60 kops/s. A read is served by the tail replica in a single round trip rather than traversing the chain, which is why read latency sits well below append latency. Compared with Corfu, Corfu-v adds 6.1%–13.1% to append latency and 0.9%–16.2% to read latency.
We evaluate Corfu-v during crash recovery using 40 append-only clients (Figure 11). When the head of the chain fails, the coordinator shrinks the chain from 3 replicas to 2. Appends then traverse a shorter chain, so latency drops. Recovery is slower than in NOPaxos for two reasons. Appends carry 4KB payloads rather than the 100–200 bytes NOPaxos replicates, and Corfu-v has no snapshot support, so a rejoining replica must fetch every log entry from scratch. This catch-up takes up to 40 seconds. Once it completes, the chain regains its original length and latency returns to its initial level.
Figure 11. Corfu-v crash recovery
LazyLog-v. We deploy LazyLog and LazyLog-v with 3 sequencers and 1 shard, and compare them under the same two workloads as Corfu. LazyLog (Figure 12) achieves much lower append latency than Corfu (Figure 10), because it lazily binds records to their global linearizable order. The trade-off is higher read latency, because a read must wait until its target log position becomes stable. Between the two LazyLog implementations, LazyLog-v’s append latency stays very close to LazyLog’s as we increase the number of clients (Figure 12a), and its saturation throughput at 50 clients is within 5.8% of LazyLog’s.

Figure 12. LazyLog vs. LazyLog-v
Under the mixed workload (Figure 12b), LazyLog-v’s read latency is even lower than LazyLog’s. This gap mainly stems from how the two implementations perform background ordering. The open-source implementation delegates it to a separate server (cons_srv in [45]), which fetches metadata from the leader sequencer and then synchronizes with the replicas. This indirection lengthens the background-ordering path and delays the advance of the stable point (stable-gp), which in turn adds latency to reads. LazyLog-v instead follows the design in the LazyLog paper (Figure 1c), in which the leader sequencer performs background ordering itself, and thus achieves lower read latency.
We evaluate LazyLog-v during crash recovery using 10 append-only clients (Figure 13), which drive about the same throughput as the 40 clients in the Corfu-v experiment (Figure 11). In Corfu-v, a shorter chain lowers latency. In LazyLog-v, an append always commits in a single round trip, so latency stays nearly flat across the crash and the rejoin. Recovery, however, is slower than in Corfu-v. Because LazyLog keeps request metadata on the sequencers and payload data on the replicas, its recovery requires more complex synchronization between them. This synchronization adds several seconds to both the recovery time and the rejoin time.
Figure 13. LazyLog-v crash recovery
Discussion
Language support. Stephen currently supports Go programs via Goose [11] and Grove [50], which covers the languages used by our target systems. However, Goose does not yet support the full Go language. For example, it does not support returning directly from within a for loop, and it does not handle short-circuit evaluation in if conditions gracefully, which can lead to branch explosion. Improving Goose’s Go coverage would make it easier to develop verified systems that achieve both high performance and strong assurance. More broadly, we believe it is possible to develop translators from other languages (e.g., P4, Rust) into Grove, which would allow Stephen to apply to a wider range of systems.
Beyond linearizability. Stephen targets strong consistency (linearizability), but many practical systems provide weaker consistency guarantees that are equally subtle and deserve rigorous verification. For example, distributed snapshot protocols [9, 13] are typically concerned with serializability, and CockroachDB describes its consistency model as lying between serializability and strict serializability [3]. We believe Stephen can be extended to verify such weaker consistency properties, and we leave this direction to future work.
Related Work
SAC systems. The complexity and performance demands of coordination systems have motivated decoupling ordering from durability, leading to a broad class of sequencer-aided coordination (SAC) systems. We demonstrate Stephen on Corfu [6, 7], NOPaxos [39] and LazyLog [44], but many others in this family could benefit. NeoBFT [51] and SwitchBFT [64] accelerate BFT consensus with Byzantine-resilient sequencers, and their linearizability proofs fit Stephen naturally. Eris [38] and Hydra [17] extend the design of NOPaxos and should also be within reach of Stephen, with additional refinement-based reasoning [5, 20, 24]. Timestamp-based protocols [22, 23, 63], which order requests by nonconsecutive timestamps, can also be viewed as SAC systems; verifying them is an important direction for future work.
Formal verification frameworks. Stephen builds on a line of Rocq (Coq) [54] verification frameworks. Iris [28] provides higher-order concurrent separation logic; Perennial [10] extends Iris with crash reasoning and incorporates Goose [11] to verify Go programs; and Grove [49, 50] adds distributed-systems primitives such as RPC, replicated state machines, and leases. We base Stephen on Grove because it offers native support for these components and prophecy variables. Stephen’s methodology is general and could in principle be applied to other verification frameworks, including Dafny [36], IronFleet [24], Verdi [62], and Verus [33].
Verified systems. Machine-checked proofs have been applied to realistic storage systems, including file systems (FSCQ [16], DFSCQ [15]), journaling (GoJournal [12]), and key-value stores (POWER [34]). These works reason about crash safety in a disk-based, single-node setting. Stephen differs in that it targets replication-based crash recovery across a broad class of distributed SAC systems.
Prophecy variables in verification. Prophecy variables were introduced by Abadi and Lamport [1, 2] and formalized in separation logic by Jung et al. [29]. They have since been used to verify local and shared-memory concurrent programs [8, 19, 58], but not crash-recoverable distributed protocols. The two prior works most closely related to Stephen are vMVCC [14], which uses prophecy variables to verify multiversion concurrency control but assumes crash-free servers, and POWER [34], which uses prophecy variables for crash consistency but under a disk-based failure model rather than replication. In contrast, Stephen uses prophecy variables to reason about crash recovery in replicated coordination protocols via cross-view prophecy peek, extending the technique to a broader class of coordination systems.
Conclusion
Modern coordination systems demand both high performance and strong correctness guarantees. Sequencer-aided coordination (SAC) protocols achieve higher performance than conventional protocols such as Paxos and VR, but they have lacked rigorous proofs of correctness. Stephen fills this gap. It introduces cross-view prophecy peek to resolve the non-determinism that crash recovery brings to the verification of SAC systems, and it adopts the escrow technique to rule out duplicate prophecy resolution during recovery. We applied Stephen to NOPaxos, Corfu and LazyLog, and uncovered several bugs in their open-source implementations. We further built verified implementations for all three protocols, which come with machine-checked linearizability proofs and yield comparable performance to their unverified counterparts.
Prophecy Peek in Corfu
Corfu’s replica set changes across views: at each view change, the coordinator chooses the replicas that serve in the next view. To decide whether commits in view , the sequencer-side proof must therefore examine the prophecy variables of exactly the replicas of , which is why every entry carries § 5.2.
Case 1: is committed during normal processing. The proof considers committed in view once every replica in the chain of has processed it. The replicas need not agree on the action: some may have processed as a Normal entry, while others, which never received it, filled its slot with Junk. As long as every replica holds an entry for ’s slot, the proof can extend the ghost log with either a Normal entry or a NOOP entry.
The recorded actions determine the entry. (1) If the proof can find a view where the s of all replicas record as Normal, the proof appends a Normal entry. (2) Otherwise, every replica’s records but no view has all replicas agreeing on Normal, and the proof appends a NOOP entry.
Case 2: is committed during recovery. As in NOPaxos, and every request before it must be fully replicated across the replicas of the new view:
Different from Case 1, if is committed during recovery, then the Corfu’s recovery protocol ensures that both and the requests prior to its position (i.e., the prefix of ) must have been fully replicated in the current view, and the type of each request is commonly agreed by all replicas, which is defined as .
Both cases reflect Corfu’s replication semantics: committing a request requires every replica in the chain rather than a majority. To determine the fate of in-flight requests, the proof peeks into later views. If neither condition holds, is never committed in this execution and the ghost log is left unchanged.
Prophecy Peek in LazyLog
In LazyLog, the peek inspects the prophecy variables of all sequencers and replicas to decide whether commits and, if so, whether as Normal or NOOP. As in NOPaxos and Corfu, it distinguishes two cases.
Case 1: is committed during normal processing. The proof considers committed in view once every sequencer and replica in has processed it. The leader sequencer extends the ghost log only for requests whose final position is the position it assigned.
The peek proceeds in two steps. First, it checks that every sequencer and replica has started normal processing in view , i.e., .
Second, it checks that the leader in is the one responsible for , i.e., . The leader assigns a local position , but that position may not be final: if the leader crashes, a leader in a later view may overwrite the position and stabilize a different order. The marker s settle this. holds in two cases. (1) The peek finds a STARTNORMAL marker of a later view whose previous view is (); inherits ’s order up to , so if , the position is decided by the leader in rather than by its successor. (2) If no later view ever starts normal processing, then the leader in remains the last leader and decides all subsequent requests.
Case 2: is committed during recovery. This case resembles Corfu with one difference: all sequencers and replicas must have completed recovery, but only the replicas must agree on the entry ’s action (Normal or NOOP), because sequencers hold no payload and always resolve their entry as Normal.
Deciding committed type. As in NOPaxos and Corfu, a committed lets the sequencer-side proof extend the ghost log atomically with an entry whose type follows in the satisfied commit condition. In LazyLog the replicas’ entry pvs decide the type: if all replicas agree on , the proof appends a Normal entry, meaning commits with its payload; otherwise it appends a NOOP entry, meaning ’s position is ultimately marked as a no-op.
References
- [1]Martín Abadi and Leslie Lamport. The existence of refinement mappings. In Proceedings of the Third Annual Symposium on Logic in Computer Science (LICS), pages 165–175, 1988.
- [2]Martín Abadi and Leslie Lamport. The existence of refinement mappings. Theoretical Computer Science, 82(2):253–284, 1991.
- [3]Matei Andrei. Cockroachdb’s consistency model, 2021.
- [4]Apache Software Foundation. Zookeeper. https://zookeeper.apache.org, 2021. Accessed: 2025-08-31.
- [5]Ralph-Johan Back and Joakim Wright. Refinement calculus: a systematic introduction. Springer Science & Business Media, 2012.
- [6]Mahesh Balakrishnan, Dahlia Malkhi, John D. Davis, Vijayan Prabhakaran, Michael Wei, and Ted Wobber. Corfu: A distributed shared log. ACM Trans. Comput. Syst., 31(4), December 2013.DOI
- [7]Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobbler, Michael Wei, and John D. Davis. CORFU: A shared log design for flash clusters. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12), pages 1–14, San Jose, CA, April 2012. USENIX Association.
- [8]Stefan Bodenmüller, John Derrick, Brijesh Dongol, Gerhard Schellhorn, and Heike Wehrheim. A fully verified persistency library. In Rayna Dimitrova, Ori Lahav, and Sebastian Wolff, editors, Verification, Model Checking, and Abstract Interpretation, pages 26–47, Cham, 2024. Springer Nature Switzerland.
- [9]in apache flink®: consistent stateful distributed stream processing. Proc. VLDB Endow., 10(12):1718–1729, August 2017.DOI
- [10]Tej Chajed, Joseph Tassarotti, M. Frans Kaashoek, and Nickolai Zeldovich. Verifying concurrent, crash-safe systems with perennial. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP ’19, page 243–258, New York, NY, USA, 2019. Association for Computing Machinery.DOI
- [11]Tej Chajed, Joseph Tassarotti, M Frans Kaashoek, and Nickolai Zeldovich. Verifying concurrent go code with goose. In Proceedings of the 6th International Workshop on Coq for Programming Languages (CoqPL), New Orleans, LA, 2020.
- [12]Tej Chajed, Joseph Tassarotti, Mark Theng, Ralf Jung, M. Frans Kaashoek, and Nickolai Zeldovich. Gojournal: a verified, concurrent, crash-safe journaling system. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21), pages 423–439. USENIX Association, July 2021.DOI
- [13]K. Mani Chandy and Leslie Lamport. Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst., 3(1):63–75, February 1985.
- [14]Yun-Sheng Chang, Ralf Jung, Upamanyu Sharma, Joseph Tassarotti, M. Frans Kaashoek, and Nickolai Zeldovich. Verifying mVCC, a high-performance transaction library using multi-version concurrency control. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23), pages 871–886, Boston, MA, July 2023. USENIX Association.
- [15]Haogang Chen, Tej Chajed, Alex Konradi, Stephanie Wang, Atalay undfinedleri, Adam Chlipala, M. Frans Kaashoek, and Nickolai Zeldovich. Verifying a high-performance crash-safe file system using a tree specification. In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP ’17, page 270–286, New York, NY, USA, 2017. Association for Computing Machinery.DOI
- [16]Haogang Chen, Daniel Ziegler, Tej Chajed, Adam Chlipala, M. Frans Kaashoek, and Nickolai Zeldovich. Using crash hoare logic for certifying the fscq file system. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP ’15, page 18–37, New York, NY, USA, 2015. Association for Computing Machinery.
- [17]Inho Choi, Ellis Michael, Yunfan Li, Dan Ports, and Jialin Li. Hydra: Serialization-free network ordering for strongly consistent distributed applications. In Proceedings of the 20th USENIX Conference on Networked Systems Design and Implementation (NSDI 2023), pages 1–16, 2023.
- [18]James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ Furman, Sanjay Ghemawat, Andrey Gubarev, and et al. Spanner: Google’s globally-distributed database. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2012), pages 251–264, 2012.
- [19]Paulo Emílio de Vilhena, François Pottier, and Jacques-Henri Jourdan. Spy game: verifying a local generic solver in iris. Proc. ACM Program. Lang., 4(POPL), December 2019.DOI
- [20]Edsger W. Dijkstra. Chapter I: Notes on structured programming, page 1–82. Academic Press Ltd., GBR, 1972.
- [21]Cong Ding, David Chu, Evan Zhao, Xiang Li, Lorenzo Alvisi, and Robert Van Renesse. Scalog: Seamless re-configuration and total order in a scalable shared log. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 325–338, Santa Clara, CA, February 2020. USENIX Association.
- [22]Jinkun Geng, Shuai Mu, Anirudh Sivaramar, and Balaji Prabhakar. Tiga: Accelerating geo-distributed transactions with synchronized clocks. In Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles, SOSP ’25, page 555–571, New York, NY, USA, 2025. Association for Computing Machinery.DOI
- [23]Jinkun Geng, Anirudh Sivaramar, Balaji Prabhakar, and Mendel Rosenblum. Nezha: Deployable and high-performance consensus using synchronized clocks. Proceedings of the VLDB Endowment, 16:629–642, 2023.DOI
- [24]Chris Hawblitzel, Jon Howell, Manos Kapritsos, Jacob R. Lorch, Bryan Parno, Michael L. Roberts, Srinath T. V. Setty, and Brian Zill. Ironfleet: Proving practical distributed systems correct. In Proceedings of the 25th Symposium on Operating Systems Principles (SOSP ’15), pages 1–17. ACM, 2015.DOI
- [25]Christopher Hodsdon, Theano Stavrinos, Ethan Katz-Bassett, and Wyatt Lloyd. Mason: Scalable, contiguous sequencing for building consistent services. Journal of Systems Research (JSys), 3(1), 2023.DOI
- [26]Dongxu Huang, Qi Liu, Qiu Cui, Zhuhe Fang, Xiaoyu Ma, Fei Xu, Li Shen, Liu Tang, Yuxing Zhou, Menglong Huang, Wan Wei, Cong Liu, Jian Zhang, Jianjun Li, Xuelian Wu, Lingyu Song, Ruoxi Sun, Shuaipeng Yu, Lei Zhao, Nicholas Cameron, Liquan Pei, and Xin Tang. Tidb: A raft-based htap database. Proceedings of the VLDB Endowment, 13(12):3072–3084, 2020.
- [27]Xin Jin, Xiaozhou Li, Haoyu Zhang, Nate Foster, Jeongkeun Lee, Robert Soulé, Changhoon Kim, and Ion Stoica. NetChain: Scale-Free Sub-RTT coordination. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18), pages 35–49, Renton, WA, April 2018. USENIX Association.arxiv.org/abs/1802.08236
- [28]Ralf Jung, Robert Krebbers, Jacques-Henri Jourdan, Aleš Bizjak, Lars Birkedal, and Derek Dreyer. Iris from the ground up: A modular foundation for higher-order concurrent separation logic. Journal of Functional Programming, 28:e20, 2018.DOI
- [29]Ralf Jung, Rodolphe Lepigre, Gaurav Parthasarathy, Marianna Rapoport, Amin Timany, Derek Dreyer, and Bart Jacobs. The future is ours: prophecy variables in separation logic. Proc. ACM Program. Lang., 4(POPL), December 2019.DOI
- [30]Anuj Kalia, Michael Kaminsky, and David Andersen. Datacenter RPCs can be general and fast. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), pages 1–16, Boston, MA, February 2019. USENIX Association.arxiv.org/abs/1806.00680
- [31]Leslie Lamport. Paxos made simple. ACM SIGACT News, 32(4):51–58, 2001.
- [32]Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. Vertical paxos and primary-backup replication. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, PODC ’09, page 312–313, New York, NY, USA, 2009. Association for Computing Machinery.DOI
- [33]Andrea Lattuada, Travis Hance, Chanhee Cho, Matthias Brun, Isitha Subasinghe, Yi Zhou, Jon Howell, Bryan Parno, and Chris Hawblitzel. Verus: Verifying rust programs using linear ghost types. Proceedings of the ACM on Programming Languages, 7(OOPSLA1):286–315, 2023.DOI
- [34]Hayley LeBlanc, Jacob R Lorch, Chris Hawblitzel, Cheng Huang, Yiheng Tao, Nikolai Zel’dovich, and Vijay Chidambaram. {PowER} never corrupts: {Tool-Agnostic} verification of crash consistency and corruption detection. In 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25), pages 839–857, 2025.
- [35]Seung-seob Lee, Yanpeng Yu, Yupeng Tang, Anurag Khandelwal, Lin Zhong, and Abhishek Bhattacharjee. Mind: In-network memory management for disaggregated data centers. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, SOSP ’21, page 488–504, New York, NY, USA, 2021. Association for Computing Machinery.DOI
- [36]K. Rustan M. Leino. Dafny: An automatic program verifier for functional correctness. In Proceedings of the 16th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR-16), volume 6355 of Lecture Notes in Computer Science, pages 348–370. Springer, 2010.
- [37]Haojuan Li, Zongpu Zhang, Chenzhen Ye, Ruohan Tang, Jian Li, Haibing Guan, Qiaoling Wang, and Pengpeng Zhou. P4kvs: A role-replica separation offloading method to achieve in-network consistency for kv stores based on p4 switches. Proc. ACM Manag. Data, 3(6), December 2025.
- [38]Jialin Li, Ellis Michael, and Dan R. K. Ports. Eris: Coordination-free consistent transactions using in-network concurrency control. In Proceedings of the 26th ACM Symposium on Operating Systems Principles (SOSP 2017), page 17, Shanghai, China, October 2017. ACM.DOI
- [39]Jialin Li, Ellis Michael, Naveen Kr. Sharma, Adriana Szekeres, and Dan R. K. Ports. Just say no to paxos overhead: Replacing consensus with network ordering. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2016), pages 395–410, Savannah, GA, November 2016. USENIX Association.DOI
- [40]Jialin Li, Ellis Michael, Naveen Kr. Sharma, Adriana Szekeres, and Dan R. K. Ports. Nopaxos implementation. https://github.com/UWsyS lab/NOPaxos, 2020.
- [41]Jialin Li, Jacob Nelson, Ellis Michael, Xin Jin, and Dan R. K. Ports. Pegasus: Tolerating skewed workloads in distributed storage with In-Network coherence directories. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 387–406. USENIX Association, November 2020.
- [42]Barbara Liskov and James Cowling. Viewstamped replication revisited. 2012.
- [43]Xuhao Luo, Shreesha G. Bhat, Jiyu Hu, Ramnatthan Alagappan, and Aishwarya Ganesan. Corfu implementation (included in lazylog repository). https://github.com/dassl-uiuc/LazyLog-Artifact/tree/main, 2024.
- [44]Xuhao Luo, Shreesha G. Bhat, Jiyu Hu, Ramnatthan Alagappan, and Aishwarya Ganesan. Lazylog: A new shared log abstraction for low-latency applications. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, SOSP ’24, page 296–312, New York, NY, USA, 2024. Association for Computing Machinery.DOI
- [45]Xuhao Luo, Shreesha G. Bhat, Jiyu Hu, Ramnatthan Alagappan, and Aishwarya Ganesan. Lazylog implementation. https://github.com/dassl-uiuc/LazyLog-Artifact/tree/scalable-tput, 2024.
- [46]Ellis Michael, Dan R. K. Ports, Naveen Kr. Sharma, and Adriana Szekeres. Recovering shared objects without stable storage [extended version]. Technical report, University of Washington, 2017. Accessed: 2025-08-31.
- [47]Microsoft. Global data distribution with azure cosmos db — under the hood. https://docs.microsoft.com/en-us/azure/cosmos-db/global-dist-under-the-hood, 2022. Accessed: 2025-08-31.
- [48]Brian M. Oki and Barbara H. Liskov. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 8–17, New York, NY, USA, August 1988. ACM.
- [49]Upamanyu Sharma. Modular verification of distributed systems with grove (master thesis), 2022.
- [50]Upamanyu Sharma, Ralf Jung, Joseph Tassarotti, Frans Kaashoek, and Nicolai Zeldovich. Grove: a separation-logic library for verifying distributed systems. In Proceedings of the 29th Symposium on Operating Systems Principles, SOSP ’23, page 113–129, New York, NY, USA, 2023. Association for Computing Machinery.DOI
- [51]Guangda Sun, Mingliang Jiang, Xin Zhe Khooi, Yunfan Li, and Jialin Li. Neobft: Accelerating byzantine fault tolerance using authenticated in-network ordering. In Proceedings of the ACM SIGCOMM 2023 Conference, ACM SIGCOMM ’23, page 239–254, New York, NY, USA, 2023. Association for Computing Machinery.DOI
- [52]Tamás Szelei and et al. rpclib. https://github.com/rpclib/rpclib, 2022.
- [53]Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan Van-Benschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Darnell, Bram Grunier, Justin Jaffray, Lucy Zhang, and Peter Mattis. Cockroachdb: The resilient geo-distributed sql database. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD ’20, page 1493–1509, New York, NY, USA, 2020. Association for Computing Machinery.DOI
- [54]The Rocq Development Team. The Rocq Prover. https://doi.org/10.5281/zenodo.15149629, 2025. Version 9.0.
- [55]The Verus Development Team. vstd: The Verus Standard Library. https://verus-lang.github.io/verus/verusdoc/vstd/, 2026. Accessed: 2026-09-08.
- [56]Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, and Daniel J. Abadi. Calvin: Fast distributed transactions for partitioned database systems. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, SIGMOD ’12, page 1–12, New York, NY, USA, 2012. Association for Computing Machinery.
- [57]Aaron Turon, Viktor Vafeiadis, and Derek Dreyer. Gps: navigating weak memory with ghosts, protocols, and separation. SIGPLAN Not., 49(10):691–707, October 2014.
- [58]Simon Friis Vindum and Lars Birkedal. Contextual refinement of the michael-scott queue (proof pearl). In Proceedings of the 10th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2021, page 76–90, New York, NY, USA, 2021. Association for Computing Machinery.DOI
- [59]Qing Wang, Youyou Lu, Erci Xu, Junru Li, Youmin Chen, and Jiwu Shu. Concordia: Distributed shared memory with In-Network cache coherence. In 19th USENIX Conference on File and Storage Technologies (FAST 21), pages 277–292. USENIX Association, February 2021.
- [60]Michael Wei, Amy Tai, Christopher J. Rossbach, Ittai Abraham, Maithem Munshed, Medhavi Dhawan, Jim Stabile, Udi Wieder, Scott Fritchie, Steven Swanson, Michael J. Freedman, and Dahlia Malkhi. vCorfu: A Cloud-Scale object store on a shared log. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pages 35–49, Boston, MA, March 2017. USENIX Association.
- [61]Michael Whittaker, Ailidani Ailijiang, Aleksey Charapko, Murat Demirbas, Neil Giridharan, Joseph M. Hellerstein, Heidi Howard, Ion Stoica, and Adriana Szekeres. Scaling replicated state machines with compartmentalization. Proc. VLDB Endow., 14(11):2203–2215, July 2021.arxiv.org/abs/2012.15762
- [62]James R. Wilcox, Doug Woos, Pavel Panchekha, Zachary Tatlock, Xi Wang, Michael D. Ernst, and Thomas Anderson. Verdi: a framework for implementing and formally verifying distributed systems. SIGPLAN Not., 50(6):357–368, June 2015.
- [63]Xinan Yan, Linguan Yang, and Bernard Wong. Domino: using network measurements to reduce state machine replication latency in wans. In Proceedings of the 16th International Conference on Emerging Network-ing Experiments and Technologies, CoNEXT ’20, page 351–363, New York, NY, USA, 2020. Association for Computing Machinery.DOI
- [64]Lior Zeno, Naama Ben-David, and Mark Silberstein. In link we trust: Bft at the speed of cft using switches. In Proceedings of the 23rd USENIX Symposium on Networked Systems Design and Implementation (NSDI 2026), 2021.






