4 ms·
I would say blockchains fit this definition. What I get away from that is that this definition is not restrictive enough. Similarly, a list of operations with
by espadrine 2y ago
I would say blockchains fit this definition. What I get away from that is that this definition is not restrictive enough.
Similarly, a list of operations with Lamport timestamps fits this definition. However, just like the blockchain, it makes no effort to preserve user intent.
To go to an extreme, a merge operation which replaces the current content with the empty string, is a CRDT per this definition.
- kiitos 2y agoBlockchains absolutely do not satisfy the definition of a CRDT.
- espadrine 2y agoHow would you change the definition so that they do not?
- jakelazaroff 2y agoMy understanding is that blockchains agree upon a shared state via consensus (i.e. coordinating with other nodes) rather than by a deterministic algorithm.
- espadrine 2y agoIt is deterministic: the local updates must be grouped into a block linking to the longest-known chain, and the block is broadcast; upon receiving a block, all nodes must locally revert operations that are no longer part of the deepest chain, and apply operations that are. It is a bit like last-writer-wins, except it uses the block history count instead of timestamps. Clearly they lose a lot of user intents. I feel like CRDTs are associated with intent preservation. Perhaps rule 2 ought to include that inconsistency resolution ought to not discard operations. That would also exclude LWW and the “empty string” merge as CRDTs.
- jakelazaroff 2y agoIMO semantic “intent preservation” is an application-level concern that can affect which CRDTs are chosen, but it’s irrespective of whether the underlying data structure is a CRDT. The rules are that state merges must be commutative, associative and idempotent; if blockchains fulfill all three criteria, I don’t see why they wouldn’t count.
- kiitos 2y ago> The rules are that state merges must be commutative, associative and idempotent; Yes! > if blockchains fulfill all three criteria, I don’t see why they wouldn’t count. Blockchains definitely do not fulfill all three criteria! > IMO semantic “intent preservation” is an application-level concern that can affect which CRDTs are chosen, but it’s irrespective of whether the underlying data structure is a CRDT. You're correct! Whether or not a data structure is a CRDT is entirely a function of whether or not its Merge operation is associative, commutative, and idempotent. Application-level concerns, including (but not limited to) semantic intent preservation, are totally irrelevant.
- jakelazaroff 2y agoOkay, back to my original skeptical position lol. I don’t understand why CRDTs seem to attract so many people claiming that their favorite computing concepts count!
- kiitos 2y agoI'm not sure what your original skeptical position is, so shrug?
- kiitos 2y agoThe "blockchain" notion of determinism you're referring to here, is far weaker than the notion of determinism used in the distsys context. This discrepancy was pretty well documented in the Jepsen analysis of the Radix DLT -- https://jepsen.io/analyses/radix-dlt-1.0-beta.35.1 https://jepsen.io/analyses/radix-dlt-1.0-beta.35.1 tl;dr: blockchains are not deterministic in the distsys sense
- kiitos 2y agoI don't need to change the definition. The existing (canonical, well-understood, etc. etc.) definition of a CRDT clearly excludes blockchain data structures.