id:"swepub:oai:DiVA.org:uu-215414"
Search: id:"swepub:oai:DiVA.org:uu-215414" > Optimal dynamic par...
- 1 of 1
- Previous record
- Next record
- To hitlist
Optimal dynamic partial order reduction
-
- Abdulla, Parosh (author)
- Uppsala universitet,Datorteknik
-
- Aronis, Stavros (author)
- Uppsala universitet,Datalogi,Programming Languages
-
- Jonsson, Bengt (author)
- Uppsala universitet,Datorteknik
- show more...
- show less...
- (creator_code:org_t)
- 2014-01-08
- 2014
- English.
- In: Proc. 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. - New York : ACM Press. - 9781450325448 ; , s. 373-384
- Conference paper (peer-reviewed)
Abstract
Subject headings
Close
- Stateless model checking is a powerful technique for program verification, which however suffers from an exponential growth in the number of explored executions. A successful technique for reducing this number, while still maintaining complete coverage, is Dynamic Partial Order Reduction (DPOR). We present a new DPOR algorithm, which is the first to be provably optimal in that it always explores the minimal number of executions. It is based on a novel class of sets, called source sets, which replace the role of persistent sets in previous algorithms. First, we show how to modify an existing DPOR algorithm to work with source sets, resulting in an efficient and simple to implement algorithm. Second, we extend this algorithm with a novel mechanism, called wakeup trees, that allows to achieve optimality. We have implemented both algorithms in a stateless model checking tool for Erlang programs. Experiments show that source sets significantly increase the performance and that wakeup trees incur only a small overhead in both time and space.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Programvaruteknik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Software Engineering (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Datorsystem (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Computer Systems (hsv//eng)
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
- Proc. 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Search for host publication in LIBRIS)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Abdulla, Parosh
- Aronis, Stavros
- Jonsson, Bengt
- Sagonas, Konstan ...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Software Enginee ...
-
- ENGINEERING AND TECHNOLOGY
- ENGINEERING AND ...
- and Electrical Engin ...
- and Computer Systems
- Articles in the publication
- Proc. 41st ACM S ...
- By the university
- Uppsala University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
