Permissiveness in transactional memories
Guerraoui R, Henzinger TA, Singh V. 2008. Permissiveness in transactional memories. DISC: Distributed Computing, LNCS, vol. 5218, 305–319.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
Author
Series Title
LNCS
Abstract
We introduce the notion of permissiveness in transactional memories (TM). Intuitively, a TM is permissive if it never aborts a transaction when it need not. More specifically, a TM is permissive with respect to a safety property p if the TM accepts every history that satisfies p. Permissiveness, like safety and liveness, can be used as a metric to compare TMs. We illustrate that it is impractical to achieve permissiveness deterministically, and then show how randomization can be used to achieve permissiveness efficiently. We introduce Adaptive Validation STM (AVSTM), which is probabilistically permissive with respect to opacity; that is, every opaque history is accepted by AVSTM with positive probability. Moreover, AVSTM guarantees lock freedom. Owing to its permissiveness, AVSTM outperforms other STMs by up to 40% in read dominated workloads in high contention scenarios. But, in low contention scenarios, the book-keeping done by AVSTM to achieve permissiveness makes AVSTM, on average, 20-30% worse than existing STMs.
Publishing Year
Date Published
2008-09-10
Acknowledgement
This research was supported by the Swiss National Science Foundation.
Volume
5218
Page
305 - 319
Conference
DISC: Distributed Computing
IST-REx-ID
Cite this
Guerraoui R, Henzinger TA, Singh V. Permissiveness in transactional memories. In: Vol 5218. Springer; 2008:305-319. doi:10.1007/978-3-540-87779-0_21
Guerraoui, R., Henzinger, T. A., & Singh, V. (2008). Permissiveness in transactional memories (Vol. 5218, pp. 305–319). Presented at the DISC: Distributed Computing, Springer. https://doi.org/10.1007/978-3-540-87779-0_21
Guerraoui, Rachid, Thomas A Henzinger, and Vasu Singh. “Permissiveness in Transactional Memories,” 5218:305–19. Springer, 2008. https://doi.org/10.1007/978-3-540-87779-0_21.
R. Guerraoui, T. A. Henzinger, and V. Singh, “Permissiveness in transactional memories,” presented at the DISC: Distributed Computing, 2008, vol. 5218, pp. 305–319.
Guerraoui R, Henzinger TA, Singh V. 2008. Permissiveness in transactional memories. DISC: Distributed Computing, LNCS, vol. 5218, 305–319.
Guerraoui, Rachid, et al. Permissiveness in Transactional Memories. Vol. 5218, Springer, 2008, pp. 305–19, doi:10.1007/978-3-540-87779-0_21.
Link(s) to Main File(s)
Access Level
Closed Access