A Probabilistic Quantitative Analysis of Probabilistic-Write/Copy-Select

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Abstract

Probabilistic-Write/Copy-Select (PWCS) is a novel synchronization scheme suggested by Nicholas Mc Guire which avoids expensive atomic operations for synchronizing access to shared objects. Instead, PWCS makes inconsistencies detectable and recoverable. It builds on the assumption that, for typical workloads, the probability for data races is very small. Mc Guire describes PWCS for multiple readers but only one writer of a shared data structure. In this paper, we report on the formal analysis of the PWCS protocol using a continuous-time Markov chain model and probabilistic model checking techniques. Besides the original PWCS protocol, we also considered a variant with multiple writers. The results were obtained by the model checker PRISM and served to identify scenarios in which the use of the PWCS protocol is justified by guarantees on the probability of data races. Moreover, the analysis showed several other quantitative properties of the PWCS protocol.

Details

OriginalspracheEnglisch
TitelNASA Formal Methods
Redakteure/-innenGuillaume Brat, Neha Rungta, Arnaud Venet
Herausgeber (Verlag)Springer, Berlin [u. a.]
Seiten307-321
Seitenumfang15
ISBN (Print)978-3-642-38087-7
PublikationsstatusVeröffentlicht - 2013
Peer-Review-StatusJa

Publikationsreihe

ReiheLecture Notes in Computer Science, Volume 7871
ISSN0302-9743

Konferenz

Titel5th NASA Formal Methods Symposium
KurztitelNFM 2013
Veranstaltungsnummer5
Dauer14 - 16 Mai 2013
BekanntheitsgradInternationale Veranstaltung
StadtMoffett Field
LandUSA/Vereinigte Staaten

Externe IDs

Scopus 84883339819
ORCID /0000-0002-5321-9343/work/142236751

Schlagworte

Schlagwörter

  • probabilistic, quantitative, probabilistic-write/copy select

Bibliotheksschlagworte