Liveness by Invisible Invariants

Yi Fang, Kenneth L. McMillan, Amir Pnueli, Lenore D. Zuck

Introduction

Verifying the correctness of "parameterized systems"—programs designed to run with an arbitrary number of processes ($N$)—is a fundamental challenge in computer science. While safety properties ("nothing bad ever happens") have seen significant progress in automation, liveness properties ("something good eventually happens") remain notoriously difficult. This paper presents a breakthrough by extending the "Invisible Invariants" method to handle liveness, effectively transforming progress checks into automated safety proofs.

Parameterized Systems and the Liveness Challenge

A parameterized system, such as a network protocol or a mutual exclusion algorithm, must function correctly whether there are two processes or two million. Proving properties for all $N$ is generally undecidable. Traditional deductive verification requires human experts to manually construct ranking functions or inductive invariants, a process that is both time-consuming and error-prone.

A parameterized mutual exclusion protocol for N processes.

The authors focus on "bounded response" properties. In finite-state systems, liveness can often be viewed as a form of safety: if a goal is reached, it must be reached within a certain number of steps. The challenge lies in finding this bound and proving it holds universally across all possible values of $N$.

The Method: From Liveness to Safety

The core of the proposed approach is the Method of Invisible Invariants. This technique uses a small instance of the system (e.g., $N=4$) to automatically generate candidate invariants using Binary Decision Diagrams (BDDs). These invariants are "invisible" because they are generated and checked by the tool without requiring user intervention.

To adapt this for liveness, the authors introduce two key innovations:

  1. Liveness Monitors: A non-interfering monitor is added to the system to track "rounds"—sequences where every process has had an opportunity to move. By showing that the system must reach its goal within $K$ rounds, the liveness property is converted into a safety property: $\square(rnd < K)$.
  2. Extended Small Model Theorem: Proving these properties often requires complex logical formulas involving both universal and existential quantifiers ($\exists \forall$). The authors provide a new theorem that allows these complex formulas to be verified by checking only a small, finite number of processes, ensuring the "invisible" approach remains mathematically sound.
Inference rules for establishing invariants in parameterized systems.

Case Studies and Results

The method was evaluated on several benchmark protocols, most notably Lamport’s Bakery algorithm. The Bakery algorithm is a classic test case for mutual exclusion that is notoriously difficult to verify due to its unbounded ticket numbers.

The authors successfully automated the proof of livelock-freedom for the Bakery protocol. Their results showed that by verifying a model with only $N=8$ processes, they could provide a mathematical guarantee that the property holds for any $N$. This represents a significant leap in automation, as it avoids the need for manual ranking functions.

Insights and Limitations

The "aha moment" of this research is the realization that for many practical systems, the time to reach a goal grows linearly with the number of processes. If this linear relationship holds, the liveness-to-safety transformation is highly effective.

However, the method does have limitations:

  • Linear Bounds: It currently cannot handle protocols with quadratic or exponential wait times.
  • Fairness: Handling "strong fairness" (compassion) remains complex and requires additional system variables.
  • State Explosion: Like all BDD-based methods, memory consumption can become a bottleneck as the number of variables or the round counter increases.

Conclusion

By bridging the gap between liveness and safety through automated invariant generation and small model theorems, this work provides a powerful tool for the formal verification of distributed systems. It moves us closer to a future where complex protocol correctness can be guaranteed with minimal human "ingenuity and expertise."

Summary updated

Abstract

The method of Invisible Invariants was developed in order to verify safety properties of parametrized systems in a fully automatic manner. In this paper, we apply the method of invisible invariant to “bounded response” properties, i.e., liveness properties of the type \( p \Rightarrow \diamondsuit q\) that are bounded – once a p-state is reached, it takes a bounded number of rounds (where a round is a sequence of steps in which each process has been given a chance to proceed) to reach a q-state – thus, they are essentially safety properties.
BibTeX
@inproceedings{fang2006liveness,
  author = {Yi Fang and Kenneth L. McMillan and Amir Pnueli and Lenore D. Zuck},
  title = {{Liveness by Invisible Invariants}},
  booktitle = {FORTE},
  year = {2006},
  doi = {10.1007/11888116\_26},
}
Figure