Completeness and nondeterminism in model checking transactional memories
Guerraoui R, Henzinger TA, Singh V. 2008. Completeness and nondeterminism in model checking transactional memories. CONCUR: Concurrency Theory, LNCS, vol. 5201, 21–35.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
Author
Series Title
LNCS
Abstract
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.
Publishing Year
Date Published
2008-07-30
Acknowledgement
This research was supported by the Swiss National Science Foundation.
Volume
5201
Page
21 - 35
Conference
CONCUR: Concurrency Theory
IST-REx-ID
Cite this
Guerraoui R, Henzinger TA, Singh V. Completeness and nondeterminism in model checking transactional memories. In: Vol 5201. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2008:21-35. doi:10.1007/978-3-540-85361-9_6
Guerraoui, R., Henzinger, T. A., & Singh, V. (2008). Completeness and nondeterminism in model checking transactional memories (Vol. 5201, pp. 21–35). Presented at the CONCUR: Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-540-85361-9_6
Guerraoui, Rachid, Thomas A Henzinger, and Vasu Singh. “Completeness and Nondeterminism in Model Checking Transactional Memories,” 5201:21–35. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008. https://doi.org/10.1007/978-3-540-85361-9_6.
R. Guerraoui, T. A. Henzinger, and V. Singh, “Completeness and nondeterminism in model checking transactional memories,” presented at the CONCUR: Concurrency Theory, 2008, vol. 5201, pp. 21–35.
Guerraoui R, Henzinger TA, Singh V. 2008. Completeness and nondeterminism in model checking transactional memories. CONCUR: Concurrency Theory, LNCS, vol. 5201, 21–35.
Guerraoui, Rachid, et al. Completeness and Nondeterminism in Model Checking Transactional Memories. Vol. 5201, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008, pp. 21–35, doi:10.1007/978-3-540-85361-9_6.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar