Transaction Ordering

[mtak-]

Transaction Ordering

[mtak-]

This is a really great question!

It seems that it is possible for two transactions to commit out of order with respect to the recorded times in the EpochLocks. Is this the case?

Yep.

I am pretty sure you get this, but just in case, the goal of swym is to have "Single Lock Atomicity" (SLA) style guarantees. Basically the outcome of those two transactions should only be the same as the purely sequential model - A=2, B=100, or A=101, B=100. It appears you agree that these are the only two outcomes when using swym.

What I hear you saying is that the version numbering on TCell's might not reflect the actual order in which values were published.

1. Yes. You totally get it :).
2. No. This out of order publishing cannot affect any other transactions. A is unreadable (due to being locked) by any third transaction for the entire duration of Tx2's commit. So this "in between" state is not observable. It is strange that the versions on the TCell's are effectively backwards from the order in which the writes "appear" to have happened using the SLA model. swym doesn't really utilize version information at a more fine grained level than simply asking the question, "was this value set sometime (doesn't matter when) before the transaction started".

In case you find it interesting (I sure do), a transaction with no read log, like Tx2 is unusual, and effectively has no constraints on it. In theory swym could guarantee that these transactions never fail, however, the commit operation may need a couple retries (due to lock acquiring failing), but the user code would only need to be run once.

Thanks for the great question!

[mtak-]

If that doesn't clear things up, feel free to ask follow up questions.

[mtak-]

Maybe looking at some cases for a Tx3 would also help.

Tx3 starts when EpochClock=0:
It can only read values A=start value, B=1

Tx3 starts when EpochClock=2:
It can only read values A=2, B=100

nontrivial case Tx3 starts when EpochClock=1:
It can only read B=100, and A is totally unreadable due to the lock being held on A, or A having a version number of 2. Therefore this transaction is doomed to retry.