Permissiveness in transactional memories Conference Paper


Author(s): Guerraoui, Rachid; Henzinger, Thomas A; Singh, Vasu
Title: Permissiveness in transactional memories
Title Series: LNCS
Affiliation
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.
Keywords: theory; STM
Conference Title: DISC: Distributed Computing
Volume: 5218
Conference Dates: September 22-24, 2008
Conference Location: Arcachon, France
Publisher: Springer  
Location: Berlin, Heidelberg
Date Published: 2008-09-10
Start Page: 305
End Page: 319
Sponsor: This research was supported by the Swiss National Science Foundation.
URL:
DOI: 10.1007/978-3-540-87779-0_21
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
  2. Vasu Singh
    17 Singh
Related IST Austria Work