Lower bounds and impossibility results for distributed transactions

Question

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?

Answer 1

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 by Masoud Saeida et al@arXiv'2013