Non-Monotonic Snapshot Isolation (arXiv'2013)

Paper Summary

This paper makes three important contributions to the theory of distributed transactions.

First, it decomposes Snapshot Isolation (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. There is another property similar to SCONS, called CONS that denotes "consistent snapshots".

Second, it proves several impossibility theorems demonstrating that SI and GPR (genuine partial replication) are incompatible. More precisely,

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).

Third, it propose a new consistency criterion, besides the existing PSI and GSI, called Non-Monotonic Snapshot Isolation (NMSI) that sidestep the impossibility theorem above.

$SI = ACA \cap CONS \cap WCF$

My Reflections:

1. From a different perspective, can we sidestep this impossibility by weakening the progress properties like OFU and WFQ, while keeping the SI safety property intact? In particular, what will be the reasonable weaker progress properties than obstruction-freedom for update transactions?

2. Or can we weakening SCONSa, SCONSb, or MON by relaxing them instead of discarding them entirely, for example, by allowing to observe stale, yet somehow bounded, snapshots. One possible way is to consider multi-copy (instead of just 1-copy) SI, which may be reasonable and desirable especially in the distributed, replicated settings.