Model checking transactional memories
Guerraoui R, Henzinger TA, Jobstmann B, Singh V. 2008. Model checking transactional memories. PLDI: Programming Languages Design and Implementation, 372–382.
Download
Conference Paper
| Published
Author
Abstract
Model checking software transactional memories (STMs) is difficult because of the unbounded number, length, and delay of concurrent transactions and the unbounded size of the memory. We show that, under certain conditions, the verification problem can be reduced to a finite-state problem, and we illustrate the use of the method by proving the correctness of several STMs, including two-phase locking, DSTM, TL2, and optimistic concurrency control. The safety properties we consider include strict serializability and opacity; the liveness properties include obstruction freedom, livelock freedom, and wait freedom.
Our main contribution lies in the structure of the proofs, which are largely automated and not restricted to the STMs mentioned above. In a first step we show that every STM that enjoys certain structural properties either violates a safety or liveness requirement on some program with two threads and two shared variables, or satisfies the requirement on all programs. In the second step we use a model checker to prove the requirement for the STM applied to a most general program with two threads and two variables. In the safety case, the model checker constructs a simulation relation between two carefully constructed finite-state transition systems, one representing the given STM applied to a most general program, and the other representing a most liberal safe STM applied to the same program. In the liveness case, the model checker analyzes fairness conditions on the given STM transition system.
Publishing Year
Date Published
2008-01-01
Page
372 - 382
Conference
PLDI: Programming Languages Design and Implementation
IST-REx-ID
Cite this
Guerraoui R, Henzinger TA, Jobstmann B, Singh V. Model checking transactional memories. In: ACM; 2008:372-382. doi:10.1145/1375581.1375626
Guerraoui, R., Henzinger, T. A., Jobstmann, B., & Singh, V. (2008). Model checking transactional memories (pp. 372–382). Presented at the PLDI: Programming Languages Design and Implementation, ACM. https://doi.org/10.1145/1375581.1375626
Guerraoui, Rachid, Thomas A Henzinger, Barbara Jobstmann, and Vasu Singh. “Model Checking Transactional Memories,” 372–82. ACM, 2008. https://doi.org/10.1145/1375581.1375626.
R. Guerraoui, T. A. Henzinger, B. Jobstmann, and V. Singh, “Model checking transactional memories,” presented at the PLDI: Programming Languages Design and Implementation, 2008, pp. 372–382.
Guerraoui R, Henzinger TA, Jobstmann B, Singh V. 2008. Model checking transactional memories. PLDI: Programming Languages Design and Implementation, 372–382.
Guerraoui, Rachid, et al. Model Checking Transactional Memories. ACM, 2008, pp. 372–82, doi:10.1145/1375581.1375626.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
Open Access
Date Uploaded
2018-12-12
MD5 Checksum
1238258a27f212fc1a2050a9a246da20
Link(s) to Main File(s)
Access Level
Closed Access