3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.