Compositional Model Checking of Consensus Protocols via Interaction-Preserving Abstraction

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

TL;DR

Researchers have developed a new framework called Interaction-Preserving Abstraction (IPA) that makes it significantly faster to verify the correctness of complex distributed systems. By breaking down TLA+ specifications into modules and simplifying their internal logic while keeping their external "behavior" intact, they achieved model-checking speedups of up to 300x for protocols like Raft.

What Problem Does This Paper Address?

Distributed consensus protocols (like Raft or Paxos) are the backbone of modern cloud databases and coordination services, ensuring that multiple machines agree on a single state even when some fail. However, verifying that these protocols are actually "correct" is notoriously difficult.

Engineers often use TLA+, a formal specification language, to model these systems. While TLA+ is excellent for finding deep, subtle bugs, it suffers from the state explosion problem: as a system gets more complex, the number of possible states the model checker (TLC) must explore grows exponentially, eventually becoming impossible to compute.

Existing "compositional" methods—which try to check parts of the system in isolation—often don't play well with TLA+’s global state model or require too much manual mathematical proof for the average engineer.

Methods

The authors propose the IPA (Interaction-Preserving Abstraction) framework. It follows a three-step workflow:

  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 authors identify "interaction variables" (shared state) and "internal variables" (private state). They then create a "coarsened" version of the module that removes internal complexity but behaves identically from the perspective of other modules.
  3. Compositional Checking: Instead of checking the whole system at once, they check each original module against the abstracted versions of all other modules.

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

Datasets

As this is a formal methods paper, "datasets" refer to the protocol specifications used for evaluation:

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

Key Insights and Ideas

  • The "Polling Pattern": In a real distributed system, a leader might poll five nodes to see who is up—a process that creates many intermediate states. In TLA+, since we have a global view, we can abstract this into a single step: "Is a majority available?" This preserves the result of the interaction while deleting thousands of unnecessary intermediate states.
  • Asynchrony Elimination: Many implementation details (like a coordinator sending a "ping" and waiting for a "pong") are transparent to other parts of the system. IPA allows developers to replace these asynchronous message exchanges with atomic global transitions during verification.
  • The Ladder of Abstraction: The authors leverage a core TLA+ philosophy: a specification isn't just one thing; it's a series of layers. IPA allows engineers to move between a "runnable design" (low-level) and a "correctness property" (high-level) more efficiently.

Key Results

The performance gains were dramatic, especially as the complexity of the models increased:

  • Raft: For a configuration with 3 commands and 1 term, direct model checking took over 19 hours. Using the IPA framework, the same check took only 4 minutes—a 288.6x speedup.
  • ParallelRaft: The framework was applied to Alibaba's production-grade protocol. While the speedups were more modest (around 3x for smaller states), it allowed the team to verify configurations that would have otherwise timed out (exceeding 200 hours) under direct checking.
  • Usability: The authors demonstrated that identifying interaction variables is intuitive for the engineers who wrote the original specs, making the framework practical for industrial use.

Limitations and Future Work

  • Manual Refinement: Currently, the "strong refinement mapping" (proving the abstract version matches the detailed version) is checked manually by introducing auxiliary variables. The authors hope to automate this in the future.
  • Liveness Properties: This work focuses on "safety" (nothing bad happens). It does not yet address "liveness" (something good eventually happens), which is another critical aspect of consensus protocols.
  • Broader Application: The authors plan to apply IPA to more complex distributed systems beyond consensus, such as distributed transactions and membership management.

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 via Interaction-Preserving Abstraction}},
  booktitle = {SRDS},
  year = {2022},
  doi = {10.1109/srds55811.2022.00018},
}
Figure