We can characterise the state of a concurrent computation by
considering the ordering of dependent events. This is a partial
order: independent events can be performed in any order without
affecting the result. DPOR is a technique for computing these
partial orders at run-time, and only testing one total order for
each partial order. This cuts down the amount of work to be done
significantly. In particular, this package implemented bounded
partial-order reduction, which is a further optimisation. Only
schedules within some *bound* are considered.
DPOR with no schedule bounding is complete, it will find all
distinct executions!
DPOR with schedule bounding is incomplete, it will only find
all distinct executions within the bound!
Caution: The fundamental assumption behind DPOR is that the
*only* source of nondeterminism in your program is the
scheduler. Or, to put it another way, if you execute the same
program with the same schedule twice, you get the same result. If
you are using this library in combination with something which
performs I/O, be *very* certain that this is the case!
See the README for more
details.
For details on the algorithm, albeit presented in a very imperative
way, see Bounded partial-order reduction, K. Coons, M. Musuvathi,
and K. McKinley (2013), available at
http://research.microsoft.com/pubs/202164/bpor-oopsla-2013.pdf