uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
The benefits of duality in verifying concurrent programs under TSO
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, Datorteknik.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.ORCID-id: 0000-0003-4993-0092
2016 (engelsk)Inngår i: 27th International Conference on Concurrency Theory: CONCUR 2016, Dagstuhl, Germany: Leibniz-Zentrum für Informatik , 2016, s. 5:1-15Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

We address the problem of verifying safety properties of concurrent programs running over the Total Store Order (TSO) memory model. Known decision procedures for this model are based on complex encodings of store buffers as lossy channels. These procedures assume that the number of processes is fixed. However, it is important in general to prove the correctness of a system/algorithm in a parametric way with an arbitrarily large number of processes.

In this paper, we introduce an alternative (yet equivalent) semantics to the classical one for the TSO semantics that is more amenable to efficient algorithmic verification and for the extension to parametric verification. For that, we adopt a dual view where load buffers are used instead of store buffers. The flow of information is now from the memory to load buffers. We show that this new semantics allows (1) to simplify drastically the safety analysis under TSO, (2) to obtain a spectacular gain in efficiency and scalability compared to existing procedures, and (3) to extend easily the decision procedure to the parametric case, which allows obtaining a new decidability result, and more importantly, a verification algorithm that is more general and more efficient in practice than the one for bounded instances.

sted, utgiver, år, opplag, sider
Dagstuhl, Germany: Leibniz-Zentrum für Informatik , 2016. s. 5:1-15
Serie
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 59
Emneord [en]
Total Store Order, Weak Memory Models, Reachability Problem, Parameterized Systems, Well-quasi-ordering
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-298663DOI: 10.4230/LIPIcs.CONCUR.2016.5ISBN: 978-3-95977-017-0 (tryckt)OAI: oai:DiVA.org:uu-298663DiVA, id: diva2:946791
Konferanse
CONCUR 2016, August 23–26, Québec City, Canada
Prosjekter
UPMARCTilgjengelig fra: 2016-08-16 Laget: 2016-07-06 Sist oppdatert: 2018-11-20

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fullteksthttp://drops.dagstuhl.de/opus/volltexte/2016/6171/pdf/LIPIcs-CONCUR-2016-5.pdf

Personposter BETA

Abdulla, Parosh AzizAtig, Mohamed FaouziNgo, Tuan Phong

Søk i DiVA

Av forfatter/redaktør
Abdulla, Parosh AzizAtig, Mohamed FaouziNgo, Tuan Phong
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 887 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf