Open Systems Laboratory at Illinois

Evaluating ordering heuristics for dynamic partial-order reduction techniques

By Steven Lauterburg, Rajesh K. Karmani, Darko Marinov, and Gul Agha. In FASE, volume 6013 of Lecture Notes in Computer Science, 308–322. Springer, 2010.

Full Text:
Download PDF
Publisher Link:


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.


    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 = "",
    keywords = "software engineering",
    pages = "308-322",
    year = "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 = "",
    isbn = "978-3-642-12028-2",
    publisher = "Springer",
    series = "Lecture Notes in Computer Science",
    volume = "6013",
    year = "2010",