# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Hitting Families of Schedules for Asynchronous Programs

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (public)

arXiv:1602.03755.pdf

(Preprint), 343KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Chistikov, D., Majumdar, R., & Niksic, F. (2016). Hitting Families of Schedules for Asynchronous Programs. Retrieved from http://arxiv.org/abs/1602.03755.

Cite as: http://hdl.handle.net/11858/00-001M-0000-002C-EB97-F

##### Abstract

We consider the following basic task in the testing of concurrent systems.
The input to the task is a partial order of events, which models actions
performed on or by the system and specifies ordering constraints between them.
The task is to determine if some scheduling of these events can result in a
bug. The number of schedules to be explored can, in general, be exponential.
Empirically, many bugs in concurrent programs have been observed to have
small bug depth; that is, these bugs are exposed by every schedule that orders
$d$ specific events in a particular way, irrespective of how the other events
are ordered, and $d$ is small compared to the total number of events. To find
all bugs of depth $d$, one needs to only test a $d$-hitting family of
schedules: we call a set of schedules a $d$-hitting family if for each set of
$d$ events, and for each allowed ordering of these events, there is some
schedule in the family that executes these events in this ordering. The size of
a $d$-hitting family may be much smaller than the number of all possible
schedules, and a natural question is whether one can find $d$-hitting families
of schedules that have small size.
In general, finding the size of optimal $d$-hitting families is hard, even
for $d=2$. We show, however, that when the partial order is a tree, one can
explicitly construct $d$-hitting families of schedules of small size. When the
tree is balanced, our constructions are polylogarithmic in the number of
events.