Testing Consensus Implementations using Communication Closure
summary
Presents a randomized tester that exploits communication closure to sample k-periodic uniform lossy synchronous executions instead of all asynchronous reorderings, reducing the sample space exponentially and prioritizing by d-bounded k-periodic isolations and recovery rate k. Implements three instrumentation modes (heavy lockstep, lightweight message-inspect, no instrumentation/timeouts) and runs against Cassandra, Ratis, Zookeeper, reproducing a known Cassandra bug, finding three Ratis bugs (one fixed) and two new Zookeeper bugs; traces are smaller and easier to debug, and the method is complete in the limit.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:12Consensus protocols for distributed systems
- 1:05Implementations of consensus protocols are prone to bugs
- 3:10Contribution
- 4:13Communication closure
- 5:30Synchronous vs asynchronous executions
- 6:10Communication-closure hypothesis for testing
- 7:33Our randomized testing algorithm
- 9:13Comparison to different algorithms
- 11:23Experiments on large-scale distributed systems
- 13:47Improved interpretability
- 14:30Summary
related talks
23mRandomized Testing of Distributed Systems with Probabilistic Guarantees
43mWhat We Talk About When We Talk About Distributed Systems
25mSafe Replication through Bounded Concurrency Verification
42mJepsen 9: A Fsyncing Feeling
40mTesting Distributed Systems w/ Deterministic Simulation
38mTowards consensus on distributed consensus #bbuzz
19mModulo: Finding Convergence Failure Bugs in Distributed Systems with Divergence...
36mTesting Stateful and Concurrent Systems Using test.check