Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Completeness and Nondeterminism in Model Checking Transactional Memories
 
conference paper

Completeness and Nondeterminism in Model Checking Transactional Memories

Guerraoui, Rachid  
•
Henzinger, Thomas A.
•
Singh, Vasu
2008
CONCUR 2008 - Concurrency Theory
Concur 2008, 19th International Conference on Concurrency Theory

Software transactional memory (STM) offers a disciplined concurrent programming model for exploiting the parallelism of modern processor architectures. This paper presents the first deterministic specification automata for strict serializability and opacity in STMs. Using an antichain-based tool, we show our deterministic specifications to be equivalent to more intuitive, nondeterministic specification automata (which are too large to be determinized automatically). Using deterministic specification automata, we obtain a complete verification tool for STMs. We also show how to model and verify contention management within STMs. We automatically check the opacity of popular STM algorithms, such as TL2 and DSTM, with a universal contention manager. The universal contention manager is nondeterministic and establishes correctness for all possible contention management schemes.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-540-85361-9_6
Web of Science ID

WOS:000259487000002

Author(s)
Guerraoui, Rachid  
Henzinger, Thomas A.
Singh, Vasu
Date Issued

2008

Published in
CONCUR 2008 - Concurrency Theory
Start page

21

End page

35

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent date
Concur 2008, 19th International Conference on Concurrency Theory

August 19-22 2008

Available on Infoscience
August 7, 2008
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/27267
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés