3 ms·
I don't understand how this can be generalized to non-deterministic systems. First off, the definition of non-deterministic is unclear to me. His definition of
by oggy 8y ago
I don't understand how this can be generalized to non-deterministic systems. First off, the definition of non-deterministic is unclear to me. His definition of deterministic seems wrong, as he's using a set of requests. Sets are unordered, so this would imply that the order in which requests execute is irrelevant - which is true for commutative operations, but Calvin doesn't seem to be limited to those.
Assuming that "deterministic" should be defined on lists of inputs, then I don't understand how the approach can be applied to nondeterministic databases. The crux seems of the approach seems to be in consistent distributed reads (which you can get by globally ordering transactions and MVCC). But for fault-tolerance, these must also be repeatable, and I don't see how to make them repeatable if the state of replicas in a shard is allowed to diverge.
- abadid 8y agoEvery 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 8y agoWhat 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 8y agoPlease see: http://www.cs.umd.edu/~abadi/papers/determinism-vldb10.pdf http://www.cs.umd.edu/~abadi/papers/determinism-vldb10.pdf