Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Multiplexing of Partially Ordered Events

Colin Campbell, Margus Veanes, Jiale Huo, and Alexandre Petrenko


This paper introduces a method to correctly order events in modelbased testing for concurrent systems, in particular multi-threaded programs, whose events are only partially ordered. For a sequential, centralized tester, we need to merge (local) traces of each component into a (global) trace of a system in such a way that the ordering constraints are observed. To this end, we instrument a multi-threaded program under test so that the order of lock events is visible. This additional information helps a so-called multiplexer to reconstruct a fully serial trace consistent with the partial order. We describe programs and the multiplexer as labeled transition systems and give pseudo-code of the algorithm implementing the latter. The implementation of the algorithm presented is used in an industrial context.


Publication typeInproceedings
Published inTestCom 2005
PublisherSpringer Verlag
> Publications > Multiplexing of Partially Ordered Events