[abadid]

Every transaction has an numeric identifier. These identifiers are used to order versions of updates to a data item. Versions from higher transaction IDs are considered to be "after" lower ones. Reading versions as of a particular version identifier must be consistent. But the system as a whole needs not be deterministic.

[oggy]

What is your definition of a nondeterministic system then? Typically it's a system with a non-deterministic transition relation. E.g., assuming for simplicity a system state sharded into two shards with numerical states, and the initial system state (0, 0), a non-deterministic operation can take (0, 0) to either (1, 1) or (2, 2). Then if you let each shard's replicas run independently, you could end up in an inconsistent state (either (1, 2) or (2, 1)).

So I suppose that your definition of nondeterministic must differ, but I can't figure out how.

[abadid]

Please see: http://www.cs.umd.edu/~abadi/papers/determinism-vldb10.pdf