Compositional Model Checking of Consensus Protocols Specified in TLA+ via Interaction-Preserving Abstraction

Xiaosong Gu, Wei Cao, Yicong Zhu, Xuan Song, Yu Huang, Xiaoxing Ma

Abstract

Consensus protocols are widely used in building reliable distributed software systems and its correctness is of vital importance. TLA+ is a lightweight formal specification language which enables precise specification of system design and exhaustive checking of the design without any human effort. The features of TLA+ make it widely used in the specification and model checking of consensus protocols, both in academia and industry. However, the application of TLA+ is limited by the state explosion problem in model checking. Though compositional model checking is essential to tame the state explosion problem, existing compositional checking techniques do not sufficiently consider the characteristics of TLA+. In this work, we propose the Interaction-Preserving Abstraction (IPA) framework, which leverages the features of TLA+ and enables practical and efficient compositional model checking of consensus protocols specified in TLA+. In the IPA framework, system specification is partitioned into multiple modules, and each module is divided to the internal part and the interaction part. The basic idea of the interaction-preserving abstraction is to omit the internal part of each module, such that another module cannot distinguish whether it is interacting with the original module or the coarsened abstract one. We use the IPA framework to the compositional checking of the TLA+ specification of two consensus protocols Raft and ParallelRaft. We demonstrate that the IPA framework is easy to use in realistic scenarios and at the same time significantly reduces the model checking cost.

Introduction

Distributed consensus protocols, such as Raft or Paxos, form the backbone of modern cloud databases and coordination services. They ensure that multiple machines agree on a single state even in the presence of failures. However, verifying the correctness of these protocols is notoriously difficult due to their inherent complexity.

Engineers frequently use TLA+, a formal specification language, to model these systems. While TLA+ is excellent for uncovering subtle bugs, it suffers from the state explosion problem: as system complexity increases, the number of possible states the model checker (TLC) must explore grows exponentially, often making computation impossible. Existing compositional methods—which attempt to check system components in isolation—frequently struggle with TLA+’s global state model or require excessive manual mathematical proof.

The IPA Framework

To address these challenges, the researchers developed the Interaction-Preserving Abstraction (IPA) framework. This framework enables practical and efficient compositional model checking by leveraging the specific features of TLA+. The IPA workflow consists of three main steps:

  1. Modular Partitioning: The system specification is divided into functional modules (e.g., "Leader Election" vs. "Log Replication").
  2. Interaction-Preserving Abstraction: For each module, the framework distinguishes between "interaction variables" (shared state) and "internal variables" (private state). A "coarsened" abstract version of the module is created by removing internal complexity while ensuring it behaves identically from the perspective of other modules.
  3. Compositional Checking: Instead of checking the entire system at once, each original module is checked against the abstracted versions of all other modules.
The three-step workflow of the Interaction-Preserving Abstraction (IPA) framework, illustrating modular partitioning, abstraction, and compositional checking.

The paper provides a formal proof that if these individual compositional checks pass, the original complex system is mathematically guaranteed to be correct.

Evaluation and Results

The IPA framework was evaluated using two significant protocol specifications:

  • Raft: The industry-standard consensus protocol.
  • ParallelRaft: A specialized replication protocol used in PolarFS, the distributed file system for Alibaba’s commercial database, PolarDB.

The performance gains were dramatic, particularly as model complexity increased. For a Raft configuration with 3 commands and 1 term, direct model checking took over 19 hours. Using the IPA framework, the same check was completed in only 4 minutes—a 288.6x speedup. For ParallelRaft, the framework allowed the team to verify configurations that would have otherwise timed out (exceeding 200 hours) under direct checking, achieving roughly a 3x speedup for smaller states.

Key Insights

  • The Polling Pattern: In distributed systems, a leader might poll multiple nodes to determine their status, creating numerous intermediate states. IPA abstracts this into a single step (e.g., "Is a majority available?"), preserving the interaction result while eliminating thousands of unnecessary states.
  • Asynchrony Elimination: Many implementation details, such as "ping-pong" message exchanges, are transparent to other system parts. IPA allows replacing these asynchronous exchanges with atomic global transitions during verification.
  • The Ladder of Abstraction: By leveraging TLA+'s philosophy of layered specifications, IPA enables engineers to move efficiently between a low-level "runnable design" and a high-level "correctness property."

Conclusion and Future Work

While the IPA framework significantly reduces model-checking costs, some areas for improvement remain. Currently, proving that an abstract version matches the detailed version (strong refinement mapping) requires manual effort through auxiliary variables. Future work aims to automate this process. Additionally, while this work focuses on "safety" properties, the authors plan to extend the framework to address "liveness" properties and apply it to broader distributed systems like membership management and distributed transactions.

Reference: Gu, X., et al. (2022). Compositional Model Checking of Consensus Protocols Specified in TLA+ via Interaction-Preserving Abstraction. arXiv:2202.11385v1 [cs.DC].

Summary updated

Abstract

Consensus protocols are widely used in building reliable distributed software systems and its correctness is of vital importance. TLA+ is a lightweight formal specification language which enables precise specification of system design and exhaustive checking of the design without any human effort. The features of TLA+ make it widely used in the specification and model checking of consensus protocols, both in academia and industry. However, the application of TLA+ is limited by the state explosion problem in model checking. Though compositional model checking is essential to tame the state explosion problem, existing compositional checking techniques do not sufficiently consider the characteristics of TLA+. In this work, we propose the Interaction-Preserving Abstraction (IPA) framework, which leverages the features of TLA+ and enables practical and efficient compositional model checking of consensus protocols specified in TLA+. In the IPA framework, system specification is partitioned into multiple modules, and each module is divided to the internal part and the interaction part. The basic idea of the interaction-preserving abstraction is to omit the internal part of each module, such that another module cannot distinguish whether it is interacting with the original module or the coarsened abstract one. We use the IPA framework to the compositional checking of the TLA+ specification of two consensus protocols Raft and ParallelRaft. Raft is a consensus protocol which is originally developed in the academia and then widely used in industry. ParallelRaft is the replication protocol in PolarFS, the distributed file system for the commercial database Alibaba PoloarDB. We demonstrate that the IPA framework is easy to use in realistic scenarios and at the same time significantly reduces the model checking cost.
BibTeX
@inproceedings{gu2022compositional,
  author = {Xiaosong Gu and Wei Cao and Yicong Zhu and Xuan Song and Yu Huang and Xiaoxing Ma},
  title = {{Compositional Model Checking of Consensus Protocols Specified in TLA+ via Interaction-Preserving Abstraction}},
  booktitle = {SRDS},
  year = {2022},
  doi = {10.1109/srds55811.2022.00018},
}
Figure