The push/pull model of transactions

Eric Koskinen, Matthew Parkinson

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We present a general theory of serializability, unifying a wide range of transactional algorithms, including some that are yet to come. To this end, we provide a compact semantics in which concurrent transactions PUSH their effects into the shared view (or UNPUSH to recall effects) and PULL the effects of potentially uncommitted concurrent transactions into their local view (or UNPULL to detangle). Each operation comes with simple criteria given in terms of commutativity (Lipton's left-movers and right-movers). The benefit of this model is that most of the elaborate reasoning (coinduction, simulation, subtle invariants, etc.) necessary for proving the serializability of a transactional algorithm is already proved within the semantic model. Thus, proving serializability (or opacity) amounts simply to mapping the algorithm on to our rules, and showing that it satisfies the rules' criteria.

Original languageEnglish
Pages (from-to)186-195
Number of pages10
JournalACM SIGPLAN Notices
Volume50
Issue number6
DOIs
StatePublished - Jun 2015

Keywords

  • Abstract data-types
  • Commutativity
  • Movers
  • Push/Pull transactions
  • Transactional boosting
  • Transactional memory

Fingerprint

Dive into the research topics of 'The push/pull model of transactions'. Together they form a unique fingerprint.

Cite this