Node-Centric Systematic Testing for Distributed Systems

Distributed systems consist of multiple independent nodes that communicate over a network. Existing testing approaches typically treat a distributed system as a whole and explore nondeterministic event interleavings to uncover bugs. However, the exponential growth of node state combinations severely limits scalability, making exhaustive testing impractical. We observe that systematically testing individual node behaviors is sufficient to cover overall system behaviors, while avoiding the combinatorial explosion caused by states irrelevant to the executing node. Motivated by this insight, we propose node-centric equivalence , which is orthogonal to existing independence and symmetry equivalences, to identify equivalent state transitions. We first identify node-centric equivalence groups among state transitions according to their projected node-centric behaviors, and then systematically explore each node's unique behaviors without traversing the full interleaving space of distributed systems, while preserving bug detection capability. Based on node-centric equivalence, we develop a testing tool, NodeExplore and evaluate NodeExplore on five real-world distributed systems. The results show that NodeExplore detects bugs up to 27 \(\times\) faster, reduces test execution time by over 98%, and uncovers 11 new bugs, demonstrating its efficiency and practicality.