Evaluating ordering heuristics for dynamic partial-order reduction techniques
By
Actor programs consist of a number of concurrent objects called actors, which communicate by exchanging messages. Nondeterminism in actors results from the different possible orders in which available messages are processed. Systematic testing of actor programs explores various feasible message processing schedules. Dynamic partial-order reduction (DPOR) techniques speed up systematic testing by pruning parts of the exploration space. Based on the exploration of a schedule, a DPOR algorithm may find that it need not explore some other schedules. However, the potential pruning that can be achieved using DPOR is highly dependent on the order in which messages are considered for processing. This paper evaluates a number of heuristics for choosing the order in which messages are explored for actor programs, and summarizes their advantages and disadvantages.
BibTeX
@inproceedings{conf/fase/LauterburgKMA10,
author = "Lauterburg, Steven and Karmani, Rajesh K. and Marinov,
Darko and Agha, Gul",
editor = "Rosenblum, David S. and Taentzer, Gabriele",
title = "Evaluating Ordering Heuristics for Dynamic Partial-Order
Reduction Techniques",
booktitle = "FASE",
crossref = "conf/fase/2010",
ee = "http://dx.doi.org/10.1007/978-3-642-12029-9_22",
keywords = "software engineering",
pages = "308-322",
year = "2010",
}
@proceedings{conf/fase/2010,
editor = "Rosenblum, David S. and Taentzer, Gabriele",
title = "Fundamental Approaches to Software Engineering, 13th
International Conference, FASE 2010, Held as Part of the Joint
European Conferences on Theory and Practice of Software, ETAPS
2010, Paphos, Cyprus, March 20-28, 2010. Proceedings",
ee = "http://dx.doi.org/10.1007/978-3-642-12029-9",
isbn = "978-3-642-12028-2",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
volume = "6013",
year = "2010",
}