Randomized Testing of Distributed Systems with Probabilistic Guarantees
summary
A randomized scheduler called PC-TCP constructs an online chain partition of the observed partial order and samples schedules so that for width w and n events it guarantees discovering a bug of depth d with probability at least 1/(w^2 n^{d-1}) by sampling at most w^2 n^{d-1} schedules; proofs use online dimension and adaptive chain partitioning. A prototype tests P# models and real systems Zookeeper and Cassandra, finding a deep Cassandra bug reliably when naive random walk does not.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:21Distributed systems are prone to bugs!
- 1:20Testing is a practical approach
- 2:05PCTCP on an example
- 5:35Bug depth: Minimum tuple of events to expose the bug
- 6:41Coverage: Strong d-Hitting families of schedules
- 8:50Realizer and dimension of a poset
- 9:40Adaptive chain covering - Online dimension algorithm
- 12:22Strong d-hitting family - Adaptive chain covering
- 14:40Experimental results - Cassandra
- 18:29Summary
related talks
15mTesting Consensus Implementations using Communication Closure
40mProperty-testing async code in Rust to build reliable distributed systems
14mFeedback-guided Adaptive Testing of Distributed Systems Designs
45mRandomized testing: Gotta Catch ‘Em All
40mTesting Distributed Systems w/ Deterministic Simulation
18mEfficient Exposure of Partial Failure Bugs in Distributed Systems with Inferred...
27mUnderstanding Distributed Systems with Deterministic Simulation
10mNerv: Probabilistic Dynamic Partial Order Reduction for Hardware