Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Optimal dynamic partial order reduction
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi. (Programming Languages)
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi. (Programming Languages)
2014 (Engelska)Ingår i: Proc. 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New York: ACM Press, 2014, 373-384 s.Konferensbidrag (Refereegranskat)
Abstract [en]

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.

Ort, förlag, år, upplaga, sidor
New York: ACM Press, 2014. 373-384 s.
Serie
ACM SIGPLAN NOTICES, ISSN 0362-1340 ; 49:1
Nationell ämneskategori
Programvaruteknik Datorsystem
Identifikatorer
URN: urn:nbn:se:uu:diva-215414DOI: 10.1145/2535838.2535845ISI: 000331120500032ISBN: 978-1-4503-2544-8 (tryckt)OAI: oai:DiVA.org:uu-215414DiVA: diva2:687063
Konferens
POPL 2014, January 22-24, San Diego, CA
Projekt
UPMARCRELEASEProFuN
Forskningsfinansiär
EU, FP7, Sjunde ramprogrammet, 287510
Tillgänglig från: 2014-01-13 Skapad: 2014-01-13 Senast uppdaterad: 2015-05-05Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Abdulla, ParoshAronis, StavrosJonsson, BengtSagonas, Konstantinos
Av organisationen
DatorteknikDatalogi
ProgramvaruteknikDatorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar

Altmetricpoäng

Totalt: 991 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf