Non-blocking transactional atomicity

Very cool and simple. The notion of "time" may be a bit misleading but actually the client just requires to generate an unguessable rand, think at it like getting a string from /dev/urandom, so actually time is completely not part of the protocol which is great (also avoiding to deal with client IDs can be nice in practice).

The algorithm does seem nicer than a 2PC protocol in that there is no need for a 2PC coordinator. By distributing the metadata as it does the clients and servers can figure out what has been committed and what hasn't. However it doesn't appear to directly include semantics for aborting transactions which is a pretty important part of a distributed transaction protocol.

The paper admits the algorithm does not guarantee termination but I would have liked to see more details on the failure scenarios regardless (minor details in footnote 3). It's not clear to me what writers see (if anything) when a write fails.

The paper does talk about how non-overlapping transactions won't block each other (which is nice but not a solution) and how one could add the ability to abort and trigger a cleanup by the use of a good (user supplied) failure detection module. But having a reliable node failure monitor that can react fast enough to ensure availability is really the hard part.

Would love to see more on aborting transactions next.

> However it doesn't appear to directly include semantics for aborting transactions which is a pretty important part of a distributed transaction protocol.

Yep, I left this out to avoid confusion at first. There are some details in the "What just happened?", but the basic idea is that any aborted write will be stuck in "pending." Same for failed writes; writers won't see these. The algorithm presented actually guarantees "Read Committed" ACID isolation.

> But having a reliable node failure monitor that can react fast enough to ensure availability is really the hard part.

Well, you'll remain available for reads and writes, but the size of "pending" might grow. You essentially need asynchronous distributed garbage collection, which will stall in the presence of partitions and may require the failure detectors I mentioned.

> The paper does talk about how non-overlapping transactions won't block each other (which is nice but not a solution)

I don't see how this isn't a solution for transactions that desire last-writer-wins semantics. If, as in the examples I listed, writes commute, then a blocked write shouldn't stall others. If you want to prevent Lost Update or Write Skew anomalies (i.e., concurrent update), then you'll have to give up availability and/or block.

If you clear metadata, the following pathological case results in an inconsistent read:

* x = 0 and y = 0, starting out in the "good" state with metadata cleared;

* client A reads x with no metadata, then for whatever reason blocks or is delayed;

* client B writes x = 1 and y = 1, completes the transaction, and the metadata is cleared;

* client A reads y = 1.

This shouldn't be an issue unless you aggressively clear metadata and have a long-running client.

In that case, if client A wants to do something with the value x, it should instruct the server to place metadata on it, essentially saying that it's reading it with the intent to update. This could be implemented as "update x with value of get(x)". That way it would be placed into pending with metadata.

Having a heartbeat between the client and the server could also help prevent the write from getting purged from "pending" prematurely.