💻 computer science

Almost Fair Simulations

This paper introduces a family of "almost fair" simulation relations for transition systems with Büchi fairness conditions that simplify reasoning through intuitive deductive rules, offering a more accessible alternative to complex standard fair simulations for proving fair trace inclusion in interactive verification.

Original authors: Arthur Correnson, Iona Kuhn, Bernd Finkbeiner

Published 2026-05-27

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Arthur Correnson, Iona Kuhn, Bernd Finkbeiner

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Fairness" Problem in Computer Verification

Imagine you are trying to prove that a complex computer program (the Source) behaves correctly according to a set of rules (the Target).

In the world of computer science, there are two main types of rules:

Safety Rules: "Nothing bad ever happens." (e.g., The program never crashes, or never divides by zero).
Liveness Rules: "Something good eventually happens." (e.g., The program eventually finishes its task, or eventually prints "Done").

For Safety Rules, we have a powerful, easy tool called Simulation. Think of this like a shadow puppet show. If you can prove that every move the Source makes can be perfectly mimicked by the Target, you know the Source is safe. It's like saying, "If the shadow never does anything scary, the hand casting it is safe."

However, Liveness Rules are tricky. They require the system to keep moving and eventually reach a "good" state forever. Standard simulation fails here because it doesn't care about when things happen, only if they happen. It's like checking if a runner finishes a race, but ignoring whether they stop halfway to take a nap.

The Old Solution: The "Strict Synchronization" Problem

To fix this, researchers invented Fair Simulation. This adds a rule: "The Source and Target must visit 'good' states (like a finish line) infinitely often."

The first version of this was Direct Simulation.

The Analogy: Imagine two dancers. Direct Simulation demands that if the Source dancer steps on a "good" spot on the floor, the Target dancer must step on a "good" spot at the exact same moment.
The Problem: This is too strict. In real life, a program might take a variable amount of time to finish a task (maybe it waits for a user to click a button), while the specification (the rulebook) expects a precise timing. If the program is just 1 second late, Direct Simulation says "Fail," even though the program is actually doing the right thing. It's like failing a runner because they crossed the finish line one second after the clock stopped, even though they ran the whole race.

The Paper's Solution: "Almost Fair" Simulations

The authors of this paper argue that we don't need such strict synchronization. They propose a family of new, more flexible tools called "Almost Fair Simulations." They built these tools specifically to be used by humans (interactive verification) inside a proof assistant (a tool that helps mathematicians and programmers check their logic), rather than just for computers to run automatically.

Here is the progression of their new tools:

1. Delay Simulation (The "Grace Period" Approach)

The Idea: Instead of demanding the Target match the Source's "good" steps instantly, we allow the Target to delay.
The Analogy: The Source says, "I'm stepping on the good spot now!" The Target replies, "Okay, I'll step on a good spot too, but I might need to take a few extra steps first to get there."
How it works: The Target is allowed to wander around for a while (a bounded number of steps) as long as it eventually hits a good spot. This handles the "variable timing" problem of real programs.
The Catch: Even this is sometimes too rigid. If the Source has a "good" spot that it visits unnecessarily (a false alarm), the Target gets forced to chase it, even if the Target doesn't need to.

2. Right-Biased Delay Simulation (The "Ignore the Left" Approach)

The Idea: Sometimes, the Source program has "good" spots that are just noise (it's a safety program, not a liveness one).
The Analogy: Imagine the Source is a noisy machine that beeps happily every time it does anything. The Target is a quiet machine that only beeps when it actually finishes a job.
The Solution: This tool tells the verifier: "Ignore the Source's beeps. Just make sure the Target eventually finishes its job." It focuses entirely on the Target's ability to succeed, ignoring the Source's specific timing of "good" moments. This is great for proving that a program meets a specification, even if the program itself doesn't have strict liveness rules.

3. Double Delay Simulation (The "Skip the Start" Approach)

The Idea: Sometimes, the Source program has a "bad" start. It visits a "good" spot early on, but that visit is irrelevant to the long-term goal.
The Analogy: The Source starts a race, trips over a hurdle (visiting a "good" spot by accident), and then runs the rest of the race. The Target doesn't need to trip over a hurdle to match it.
The Solution: This tool allows the verifier to say, "Let's ignore the first few 'good' visits by the Source." It lets you skip the beginning of the proof to get to the part that actually matters.

4. Repeated Delay Simulation (The "Reset Button" Approach)

The Idea: This is the most powerful tool. It combines the previous ideas.
The Analogy: Imagine a game where you have to collect coins infinitely. The Source collects a coin, then runs a long loop, then collects another. The Target doesn't need to match the timing of every coin.
The Solution: Every time the Target successfully collects a "good" coin (reaches a good state), it gets a free pass. It can say, "Okay, I just hit a good state. Now, I can ignore the Source's next few 'good' states and start my own timer again."
Why it matters: This allows the Target to handle complex loops where the Source might have "fake" good states scattered throughout. The Target can reset its "delay timer" whenever it succeeds, making the proof much easier to construct.

How They Proved It Works

The authors didn't just invent these ideas; they built them inside a Proof Assistant (a digital tool called Rocq, similar to a super-strict math tutor).

The Deductive System: They created a set of simple "rules of the road" (like a game manual) for humans to follow. Instead of guessing the whole proof at once, you can build it step-by-step.
The "Guard" Mechanism: They used a clever trick where you can "guard" your assumptions. If you get stuck, you can pause, add more information to your "hypothesis box," and then continue. This makes the interactive process of proving these complex liveness properties much less frustrating for humans.

Summary

The paper solves a specific headache in computer verification: How do we prove a program will eventually do the right thing, without getting bogged down by the exact timing of every single step?

They moved from a Strict Synchronization (Direct Simulation) to a Grace Period (Delay), and finally to a Flexible, Resettable System (Repeated Delay). These new tools allow human experts to interactively prove that complex programs satisfy "eventually" requirements, even when the programs and the rules don't move in perfect lockstep.

Key Takeaway: They made it easier for humans to prove that software will "eventually" work correctly, by giving the software more flexibility on when it does the right thing, as long as it does do it.

Technical Summary: Almost Fair Simulations

Problem Statement

Standard simulation techniques are effective for proving safety properties (trace inclusion) but fail to prove liveness properties, which require reasoning about infinite executions and fairness conditions. While fairness-preserving simulations exist in the literature to address this, their application to interactive deductive verification (specifically within proof assistants) has been underexplored.

The primary obstacle is that existing definitions of fair simulation often involve complex nestings of inductive and coinductive relations. These definitions are difficult to reason about manually and do not easily translate into intuitive deductive systems for interactive proofs. Furthermore, existing strong notions (like direct simulation) are often too restrictive for practical verification tasks where the timing of accepting state visits differs between a program and its specification.

Methodology

The authors propose a family of "almost fair" simulation relations tailored for Büchi automata (transition systems with a set of accepting states that must be visited infinitely often). The methodology relies on three core pillars:

Parameterized Coinduction: Instead of guessing a global coinduction hypothesis upfront, the authors utilize the framework of parameterized coinduction (Hur et al.). This allows for incremental reasoning where the proof context (the set of assumed related state pairs) can be built up dynamically during the proof.
Deductive Systems: For each simulation relation, the authors derive a set of intuitive reasoning rules (a deductive system). These rules operate on triples of the form $H \vdash s_1 \preceq s_2$ , where $H$ is the current hypothesis (context), and the triple indicates that state $s_1$ is simulated by $s_2$ relative to $H$ .
Progressive Relaxation: The paper starts with established strong notions and progressively introduces weaker, more flexible notions to handle cases where stronger relations fail.

Key Contributions

1. Formalization of Direct and Delay Simulation

The authors formalized Direct Simulation and Delay Simulation for Büchi automata in the Rocq proof assistant (formerly Coq).

Direct Simulation: Requires that every visit to an accepting state in the source is synchronized with a visit to an accepting state in the target. While sound, it is often too strong for interactive proofs because it is sensitive to the exact number of steps between accepting visits.
Delay Simulation: Allows the target system to "delay" matching an accepting state visit from the source by a bounded number of steps. It is defined via a nesting of a coinductive relation ( $fsim^L_{delay}$ ) and an inductive relation ( $fsim^R_{delay}$ ). The authors provide a deductive system for this, including rules to handle the transition between "tracking left-accepting states" and "searching for a right-accepting state."

2. Identification of Limitations and Right-Biased Simulation

Through examples, the authors demonstrate that even Delay Simulation is insufficient when the source automaton contains "spurious" accepting states (states that are accepting but do not contribute to the language, or are part of cycles that cannot be matched by the target).

Right-Biased Simulation ( $fsim_{rb}$ ): A weaker notion where the simulation ignores fairness assumptions on the left (source) side entirely. It guarantees that any trace of the source is in the language of the target, provided the target visits its accepting states infinitely often. This is sufficient for verifying programs against liveness specifications when the program itself has no liveness assumptions.

3. Novel Simulations: Double and Repeated Delay

To address the limitations of Delay Simulation when the source has liveness assumptions (i.e., it is not a safety automaton), the authors introduce two new relations:

Double Delay Simulation ( $fsim_{2delay}$ ): Introduces a "wait" mechanism (via a least fixed point) that allows the prover to skip the first $n$ visits to left-accepting states before committing to the standard delay simulation logic. This handles cases where the source automaton has unnecessary initial accepting states.
Repeated Delay Simulation ( $fsim_{rdelay}$ ): Generalizes the "wait" mechanism. Instead of only skipping initial accepting states, this relation allows the prover to temporarily ignore left-accepting states every time a right-accepting state has been successfully matched. This is achieved by cycling back to a "wait" state after finding a right-accepting state, rather than immediately returning to the strict tracking mode.

Results and Mechanization

Soundness: The authors proved the soundness of all proposed simulation relations ( $fsim_{direct}$ , $fsim_{delay}$ , $fsim_{rb}$ , $fsim_{2delay}$ , $fsim_{rdelay}$ ) with respect to language inclusion of Büchi automata.
Mechanization: All definitions, soundness proofs, and the associated deductive systems were mechanized in the Rocq proof assistant.
Examples: The paper demonstrates the utility of these relations through several examples:
- Direct simulation fails on simple automata where accepting states are visited at different parities (even vs. odd steps).
- Delay simulation fails on automata with spurious accepting states in cycles.
- Double Delay and Repeated Delay successfully prove language inclusion in these previously intractable cases.
- A concrete example of a program with a countdown loop is verified against a liveness specification using Right-Biased Simulation.

Significance and Claims

The paper argues that while fair simulation is a well-studied topic in automated verification (often focusing on efficient algorithms for finite-state systems), it has been underutilized in interactive verification.

The authors claim that by re-examining these notions through the lens of interactive deductive proof, they have constructed a hierarchy of simulation relations that:

Are sound for language inclusion.
Are weaker than previous standard notions, making them applicable to a broader range of verification problems.
Admit intuitive deductive systems with reasoning rules that are easy to apply manually within a proof assistant.

The work suggests that combining carefully designed fairness-preserving simulations with parameterized coinduction provides a practical foundation for mechanized temporal reasoning, potentially serving as a basis for future fully-featured program logics for liveness properties. The authors explicitly state that they do not claim to solve the general problem of automated verification but rather provide tools to assist human-guided interactive proofs.