TY - GEN
T1 - TransDPOR
T2 - 14th IFIP International Conference on Formal Methods for Open Object-Based Distributed Systems, FMOODS 2012 and the 32nd IFIP International Conference on Formal Techniques for Networked and Distributed Systems, FORTE 2012
AU - Tasharofi, Samira
AU - Karmani, Rajesh K.
AU - Lauterburg, Steven
AU - Legay, Axel
AU - Marinov, Darko
AU - Agha, Gul
PY - 2012
Y1 - 2012
N2 - To detect hard-to-find concurrency bugs, testing tools try to systematically explore all possible interleavings of the transitions in a concurrent program. Unfortunately, because of the nondeterminism in concurrent programs, exhaustively exploring all interleavings is time-consuming and often computationally intractable. Speeding up such tools requires pruning the state space explored. Partial-order reduction (POR) techniques can substantially prune the number of explored interleavings. These techniques require defining a dependency relation on transitions in the program, and exploit independency among certain transitions to prune the state space. We observe that actor systems, a prevalent class of programs where computation entities communicate by exchanging messages, exhibit a dependency relation among co-enabled transitions with an interesting property: transitivity. This paper introduces a novel dynamic POR technique, TransDPOR, that exploits the transitivity of the dependency relation in actor systems. Empirical results show that leveraging transitivity speeds up exploration by up to two orders of magnitude compared to existing POR techniques.
AB - To detect hard-to-find concurrency bugs, testing tools try to systematically explore all possible interleavings of the transitions in a concurrent program. Unfortunately, because of the nondeterminism in concurrent programs, exhaustively exploring all interleavings is time-consuming and often computationally intractable. Speeding up such tools requires pruning the state space explored. Partial-order reduction (POR) techniques can substantially prune the number of explored interleavings. These techniques require defining a dependency relation on transitions in the program, and exploit independency among certain transitions to prune the state space. We observe that actor systems, a prevalent class of programs where computation entities communicate by exchanging messages, exhibit a dependency relation among co-enabled transitions with an interesting property: transitivity. This paper introduces a novel dynamic POR technique, TransDPOR, that exploits the transitivity of the dependency relation in actor systems. Empirical results show that leveraging transitivity speeds up exploration by up to two orders of magnitude compared to existing POR techniques.
UR - http://www.scopus.com/inward/record.url?scp=84862744754&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84862744754&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-30793-5_14
DO - 10.1007/978-3-642-30793-5_14
M3 - Conference contribution
AN - SCOPUS:84862744754
SN - 9783642307928
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 219
EP - 234
BT - Formal Techniques for Distributed Systems - Joint 14th IFIP WG 6.1 International Conference, FMOODS 2012 and 32nd IFIP WG 6.1 International Conference, FORTE 2012, Proceedings
Y2 - 13 June 2012 through 16 June 2012
ER -