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.
LMC achieves efficiency through several key innovations:
- Network Abstraction: Instead of a per-state network, LMC maintains a single, shared "pool" of all messages ever generated ($I^+$).
- 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.
- 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.
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