Evaluating ordering heuristics for dynamic partial-order reduction techniques

Steven Lauterburg; Rajesh K. Karmani; Darko Marinov; Gul Agha

doi:10.1007/978-3-642-12029-9_22

Evaluating ordering heuristics for dynamic partial-order reduction techniques

Steven Lauterburg, Rajesh K. Karmani, Darko Marinov, Gul Agha

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	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, Proceedings
Pages	308-322
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-12029-9_22
State	Published - 2010
Event	13th International Conference on Fundamental Approaches to Software Engineering, FASE 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010 - Paphos, Cyprus Duration: Mar 20 2010 → Mar 28 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6013 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th International Conference on Fundamental Approaches to Software Engineering, FASE 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010
Country/Territory	Cyprus
City	Paphos
Period	3/20/10 → 3/28/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-642-12029-9_22

Library availability

Discover UIUC Full Text

Cite this

Lauterburg, S., Karmani, R. K., Marinov, D., & Agha, G. (2010). Evaluating ordering heuristics for dynamic partial-order reduction techniques. In 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, Proceedings (pp. 308-322). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6013 LNCS). https://doi.org/10.1007/978-3-642-12029-9_22

Evaluating ordering heuristics for dynamic partial-order reduction techniques. / Lauterburg, Steven; Karmani, Rajesh K.; Marinov, Darko et al.
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, Proceedings. 2010. p. 308-322 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6013 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lauterburg, S, Karmani, RK, Marinov, D & Agha, G 2010, Evaluating ordering heuristics for dynamic partial-order reduction techniques. in 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, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6013 LNCS, pp. 308-322, 13th International Conference on Fundamental Approaches to Software Engineering, FASE 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Paphos, Cyprus, 3/20/10. https://doi.org/10.1007/978-3-642-12029-9_22

Lauterburg S, Karmani RK, Marinov D , Agha G. Evaluating ordering heuristics for dynamic partial-order reduction techniques. In 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, Proceedings. 2010. p. 308-322. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-12029-9_22

Lauterburg, Steven ; Karmani, Rajesh K. ; Marinov, Darko et al. / Evaluating ordering heuristics for dynamic partial-order reduction techniques. 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, Proceedings. 2010. pp. 308-322 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f6028e5407214d1990df8b296b6839f8,

title = "Evaluating ordering heuristics for dynamic partial-order reduction techniques",

abstract = "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 = "Steven Lauterburg and Karmani, {Rajesh K.} and Darko Marinov and Gul Agha",

note = "Copyright: Copyright 2010 Elsevier B.V., All rights reserved.; 13th International Conference on Fundamental Approaches to Software Engineering, FASE 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010 ; Conference date: 20-03-2010 Through 28-03-2010",

year = "2010",

doi = "10.1007/978-3-642-12029-9_22",

language = "English (US)",

isbn = "3642120288",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "308--322",

booktitle = "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, Proceedings",

}

TY - GEN

T1 - Evaluating ordering heuristics for dynamic partial-order reduction techniques

AU - Lauterburg, Steven

AU - Karmani, Rajesh K.

AU - Marinov, Darko

AU - Agha, Gul

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77951277706&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951277706&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-12029-9_22

DO - 10.1007/978-3-642-12029-9_22

M3 - Conference contribution

AN - SCOPUS:77951277706

SN - 3642120288

SN - 9783642120282

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 308

EP - 322

BT - 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, Proceedings

T2 - 13th International Conference on Fundamental Approaches to Software Engineering, FASE 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010

Y2 - 20 March 2010 through 28 March 2010

ER -

Evaluating ordering heuristics for dynamic partial-order reduction techniques

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this