Randomized testing of distributed systems with probabilistic guarantees
Authors:
Open Access
- 24 October 2018
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 2 (OOPSLA) , 1-28
Abstract
Several recently proposed randomized testing tools for concurrent and distributed systems come with theoretical guarantees on their success. The key to these guarantees is a notion of bug depth—the minimum length of a sequence of events sufficient to expose the bug—and a characterization of d -hitting families of schedules—a set of schedules guaranteed to cover every bug of given depth d . Previous results show that in certain cases the size of a d -hitting family can be significantly smaller than the total number of possible schedules. However, these results either assume shared-memory multithreading, or that the underlying partial ordering of events is known statically and has special structure. These assumptions are not met by distributed message-passing applications. In this paper, we present a randomized scheduling algorithm for testing distributed systems. In contrast to previous approaches, our algorithm works for arbitrary partially ordered sets of events revealed online as the program is being executed. We show that for partial orders of width at most w and size at most n (both statically unknown), our algorithm is guaranteed to sample from at most w 2 n d −1 schedules, for every fixed bug depth d . Thus, our algorithm discovers a bug of depth d with probability at least 1 / ( w 2 n d −1 ). As a special case, our algorithm recovers a previous randomized testing algorithm for multithreaded programs. Our algorithm is simple to implement, but the correctness arguments depend on difficult combinatorial results about online dimension and online chain partitioning of partially ordered sets. We have implemented our algorithm in a randomized testing tool for distributed message-passing programs. We show that our algorithm can find bugs in distributed systems such as Zookeeper and Cassandra, and empirically outperforms naive random exploration while providing theoretical guarantees.Keywords
Funding Information
- European Research Council (610150)
- Vienna Science and Technology Fund (VRG11-005)
- Austrian Science Fund (S11403-N23)
This publication has 21 references indexed in Scilit:
- Systematic testing of asynchronous reactive systems2015
- Race Detection in Two Dimensions2015
- Asynchronous programming, analysis and testing with state machinesACM SIGPLAN Notices, 2015
- Bounded Phase Analysis of Message-Passing Programs2012
- On-Line Chain Partitions of Orders: A SurveyOrder, 2011
- CassandraACM SIGOPS Operating Systems Review, 2010
- Efficient dependency tracking for relevant events in concurrent systemsDistributed Computing, 2006
- Context-Bounded Model Checking of Concurrent Software2005
- On-line chain partitions of ordersTheoretical Computer Science, 1997
- A Decomposition Theorem for Partially Ordered SetsAnnals of Mathematics, 1950