The Impossibility of Ensuring Snapshot Isolation in Genuine Replicated STMs

Masoud Saeida Ardekani 1, 2, * Pierre Sutra 1, 2 Marc Shapiro 1, 2
* Corresponding author
2 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : In order to scale to large multiprocessors or clusters, transactional memories must reduce reliance on synchronisation. Therefore, we consider two favorable formal properties, namely Snapshot Isolation (SI, by which read-only transactions commit without synchronisation), and Genuine Partial Replication (GPR, by which a processor synchronises for a transaction only if it maintains a copy of some data item accessed by that transaction). We show that, unless the read-set of every transaction is known in advance, the combination of SI+GPR is impossible. To circumvent this impossibility result, we propose to weaken SI such that snapshots are allowed to be non-monotonic.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-00932809
Contributor : Marc Shapiro <>
Submitted on : Friday, January 17, 2014 - 5:01:56 PM
Last modification on : Wednesday, June 12, 2019 - 1:34:51 AM
Long-term archiving on : Friday, April 18, 2014 - 11:51:41 AM

File

Impossibility_of_Genuine_Repli...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00932809, version 1

Citation

Masoud Saeida Ardekani, Pierre Sutra, Marc Shapiro. The Impossibility of Ensuring Snapshot Isolation in Genuine Replicated STMs. WTTM 2011: third workshop on the theory of transactional memory, Sep 2011, Roma, Italy. ⟨hal-00932809⟩

Share

Metrics

Record views

444

Files downloads

276