Search: id:"swepub:oai:DiVA.org:uu-215414" >
Optimal dynamic par...
-
Abdulla, ParoshUppsala universitet,Datorteknik
(author)
Optimal dynamic partial order reduction
- Article/chapterEnglish2014
Publisher, publication year, extent ...
-
2014-01-08
-
New York :ACM Press,2014
-
printrdacarrier
Numbers
-
LIBRIS-ID:oai:DiVA.org:uu-215414
-
https://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-215414URI
-
https://doi.org/10.1145/2535838.2535845DOI
Supplementary language notes
-
Language:English
-
Summary in:English
Part of subdatabase
Classification
-
Subject category:ref swepub-contenttype
-
Subject category:kon swepub-publicationtype
Notes
-
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 and genre
Added entries (persons, corporate bodies, meetings, titles ...)
-
Aronis, StavrosUppsala universitet,Datalogi,Programming Languages(Swepub:uu)staar721
(author)
-
Jonsson, BengtUppsala universitet,Datorteknik(Swepub:uu)bengtjs
(author)
-
Sagonas, KonstantinosUppsala universitet,Datalogi,Programming Languages(Swepub:uu)ksa25356
(author)
-
Uppsala universitetDatorteknik
(creator_code:org_t)
Related titles
-
In:Proc. 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming LanguagesNew York : ACM Press, s. 373-3849781450325448
Internet link
Find in a library
To the university's database