[ComNik]

It means that operations don't get executed in the same order on every replica. If the systems state depends on the ordering of operations, then each replica might be in a different state for the same set of operations.

"Consistent replication" would be using a protocol like Paxos to have the replicas decide on a single order of operations.

[amelius]

> If the systems state depends on the ordering of operations, then each replica might be in a different state for the same set of operations.

Which is almost always the case. Except of course, if you build your data as a growing "collection of knowledge", where the order of facts doesn't matter. But this is cheating, since you're implicitly bolting an ordering-mechanism on top of the system in this case.

[TallGuyShort]

Huh... isn't that required for being "transactional"? I should probably read the paper...

[iyzhang]

No, that was our key insight. Basically, you can think of it as, using something like Paxos requires all replicas to run the same code. So every replica checks for transaction conflicts. However, you actually only need one replica to detect a conflict, so there is no reason for every replica to run the same checks -- this is wasted work. Instead, we just make sure that each conflict is checked by at least one replica.

The other interesting conclusion is that there are other workloads like this. For example, it is possible to build a reliable and better performing lock server in this way as well (and there is an implementation in the github repo). So, you'd get something similar to Chubby, but where the latency to the server is only a single round-trip in the common case.