<p>The arXiv paper "Non-Monotonic Snapshot Isolation" [1] proves several impossibility theorems demonstrating that SI (Snapshot Isolation) and GPR (Genuine Partial Replication) are incompatible. </p>

<p>To this end, it first decomposes SI into four properties:</p>

<blockquote>
  <p>Decomposition theorem: $SI = ACA \cap SCONS \cap MON \cap WCF$</p>
</blockquote>

<p>where, </p>

<p>$ACA$: avoiding cascading aborts; $SCONS = SCONSa \cap SCONSb$: strictly consistent snapshots; $MON$: snapshot monotonicity; and $WCF$: write-conflict freedom.</p>

<p>Then, it gives the following </p>

<blockquote>
  <p>Impossibility theorem: None of SCONSa, SCONSb, and MON  is attainable in some asynchronous failure-free GPR system with obstruction-free updates (OFU) and wait-free queries (WFQ).</p>
</blockquote>

<hr>

<p>[1] <a href="http://arxiv.org/abs/1306.3906" rel="nofollow">Non-Monotonic Snapshot Isolation</a> by Masoud Saeida et al@arXiv'2013</p>

CC BY-SA 3.0
2015-01-13T03:07:18.223Z
2015-01-13T03:07:18.223Z
hengxin
<p>I am studying on distributed transactions, mainly on the correctness criteria (e.g., serializability (SR) and snapshot isolation (SI) in replicated settings) and their implementations. </p>

<p>To avoid unnecessary efforts, I would like to know that</p>

<blockquote>
  <p>What are the known (or conjectural) <strong>impossibility results and lower bounds</strong> on the complexity of implementing distributed transactions conforming to some correctness criterion and/or some progress condition?</p>
</blockquote>

<p>For example, </p>

<blockquote>
  <p>Is it possible to implement SI in a wait-free/lock-free manner in replicated settings?  </p>
</blockquote>

<reference-request><lower-bounds><dc.distributed-comp><db.databases><concurrency>
Lower bounds and impossibility results for distributed transactions
hengxin
# Lower bounds and impossibility results for distributed transactions

(Asked by: username_0 on 2014-12-24)

I am studying on distributed transactions, mainly on the correctness criteria (e.g., serializability (SR) and snapshot isolation (SI) in replicated settings) and their implementations.

To avoid unnecessary efforts, I would like to know that

> What are the known (or conjectural) **impossibility results and lower bounds** on the complexity of implementing distributed transactions conforming to some correctness criterion and/or some progress condition?

For example,

> Is it possible to implement SI in a wait-free/lock-free manner in replicated settings?

**Tags:** reference-request, lower-bounds, dc.distributed-comp, db.databases, concurrency


---

## 1 answers

### Answer by username_0 on 2015-01-13. Score: 3 | Accepted answer

The arXiv paper "Non-Monotonic Snapshot Isolation" [1] proves several impossibility theorems demonstrating that SI (Snapshot Isolation) and GPR (Genuine Partial Replication) are incompatible.

To this end, it first decomposes SI into four properties:

> Decomposition theorem: $SI = ACA \cap SCONS \cap MON \cap WCF$

where,

$ACA$: avoiding cascading aborts; $SCONS = SCONSa \cap SCONSb$: strictly consistent snapshots; $MON$: snapshot monotonicity; and $WCF$: write-conflict freedom.

Then, it gives the following

> Impossibility theorem: None of SCONSa, SCONSb, and MON is attainable in some asynchronous failure-free GPR system with obstruction-free updates (OFU) and wait-free queries (WFQ).

---

[1] [Non-Monotonic Snapshot Isolation](http://arxiv.org/abs/1306.3906) by Masoud Saeida et al@arXiv'2013


---

