Local Model Checking

Rachid Guerraoui, Maysam YabandehInfoscience 2011

Abstract

Traditional model checking for distributed systems often fails due to state space explosion, as it attempts to track global states encompassing every node and every possible network message interleaving. We explore an alternative: Local Model Checking (LMC). In this approach, the network is ignored a priori; only local node states are explored independently. The validity of a combined system state is only verified a posteriori when a potential bug is detected. This method drastically reduces the number of transitions explored. For example, while a global approach takes minutes to check a simple Paxos instance, LMC completes the task in seconds. While LMC does not eliminate exponential explosion, it postpones its effects, making it highly effective for online testing tools. We demonstrate its utility by identifying two previously unknown bugs in Paxos variants.

Introduction: The State Space Explosion

Model checking distributed systems is notoriously difficult due to the state space explosion problem. Traditional "global" model checkers track the state of every node plus the state of the network (all in-flight messages). Because the network can reorder, drop, or delay messages in countless ways, the number of possible global states grows exponentially.

Even a simple setup—like the Paxos consensus protocol with just three nodes and a single proposal—can take several minutes to check globally because the model checker must explore every possible interleaving of messages. This makes it nearly impossible to use model checking for "online" testing (checking a running system in real-time) or for complex, deep-seated bugs.

The Local Model Checking (LMC) Approach

LMC shifts the focus from global states to local node states, decoupling the nodes from the specific ordering of the network.

Conceptual difference between (a) Global State exploration and (b) the Local approach.

LMC achieves efficiency through several key innovations:

  1. Network Abstraction: Instead of a per-state network, LMC maintains a single, shared "pool" of all messages ever generated ($I^+$).
  2. Local Exploration: The model checker explores transitions based only on the local states of nodes. It doesn't care when a message was sent, only that it exists in the pool.
  3. A Posteriori Soundness Verification: Because LMC ignores the causal order of messages during exploration, it might "hallucinate" system states that are physically impossible in a real run (invalid states). To stay efficient, LMC only checks if a state is actually reachable (sound) after an invariant (a safety rule) is violated.

Implementation and Architecture

The LMC prototype was built on top of the MaceMC model checker and the CrystalBall online testing framework. The architecture decouples state exploration from invariant checking to maximize throughput.

The LMC implementation architecture, highlighting the separation of state creation, invariant checking, and soundness verification.

As shown in the architecture, Soundness Verification is only triggered when Invariant Checking returns false. This "optimistic" approach allows the tool to skip checking invariants on states that couldn't possibly violate them (e.g., states where no node has reached a "decided" status yet), saving massive amounts of computation on the vast majority of states that are safe.

Key Results

The authors evaluated LMC using complex distributed protocols including Paxos, 1Paxos, and RandTree. The results demonstrate a significant leap in performance:

  • Massive Speedup: For a 3-node Paxos instance, the classic global approach took 1514 seconds. LMC finished the same exploration in just 0.189 seconds—a ~8,000x improvement.
  • Transition Reduction: LMC reduced the number of transitions to explore from over 157,000 down to just 1,186.
  • Real Bug Discovery: The tool successfully identified two significant bugs in Paxos variants: an initialization error where roles were incorrectly assigned to the same node, and a subtle logic bug in 1Paxos caused by incorrect operator usage.

Conclusion

LMC doesn't "solve" the exponential explosion problem, but it pushes the "wall" much further back. By optimistically assuming states are reachable and only verifying the history of a state when a potential bug is found, LMC makes model checking viable for online use, where the checker restarts periodically from the current live state of a running system to look for bugs 20–30 steps ahead.

Summary updated

Abstract

Current approaches to model checking distributed systems reduce the problem to that of model checking centralized systems: global states involving all nodes and communication links are systematically explored. The frequent changes in the network element of the global states lead however to a rapid state explosion and make it impossible to model check any non-trivial distributed system. We explore in this paper an alternative: a local approach where the network is ignored, a priori: only the local nodes’ states are explored and in a separate manner. The set of valid system states is a subset of all combinations of the node local states and checking validity of such a combination is only performed a posteriori, in case of a possible bug. This approach drastically reduces the number of transitions executed by the model checker. It takes for example the classic global approach several minutes to explore the interleaving of messages in the celebrated Paxos distributed protocol even considering only three nodes and a single proposal. Our local approach explores the entire system state in a few seconds. Our local approach does clearly not eliminate the state exponential explosion problem. Yet, it postpones its manifestations till some deeper levels. This is already good enough for online testing tools that restart the model checker periodically from the current live state of a running system. We show for instance how this approach enables us to find two bugs in variants of Paxos.
BibTeX
@inproceedings{guerraoui2011local,
  author = {Rachid Guerraoui and Maysam Yabandeh},
  title = {{Local Model Checking}},
  booktitle = {Infoscience},
  year = {2011},
}
Figure