News for hackers. Stuff that matters.
Re:Faster CRDTs (2021) by espadrine on Thursday August 29, 2024 @05:45AM (#41389008)
It 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.

Re:Faster CRDTs (2021) by jakelazaroff on Thursday August 29, 2024 @07:46AM (#41389805)
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. 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.
Re:Faster CRDTs (2021) by kiitos on Thursday August 29, 2024 @05:14PM (#41395368)
> 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.

Re:Faster CRDTs (2021) by jakelazaroff on Thursday August 29, 2024 @05:25PM (#41395447)
Okay, 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!
Re:Faster CRDTs (2021) by kiitos on Thursday August 29, 2024 @05:34PM (#41395527)
I'm not sure what your original skeptical position is, so shrug?
Re:Faster CRDTs (2021) by kiitos on Thursday August 29, 2024 @05:11PM (#41395342)
The "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

tl;dr: blockchains are not deterministic in the distsys sense

Re:Faster CRDTs (2021) by espadrine on Friday August 30, 2024 @04:28AM (#41398774)
I don’t know Radix, so perhaps they use a different merge algorithm than the standard one. The article indicates, though, that nondeterminism was a bug that the company fixed. It does sound like it relies on validators, so perhaps they don’t have open membership, thus don’t allow updates from arbitrary nodes without going through those validators?

Either way, the standard blockchain algorithm doesn’t behave like that.

To be fair, I don’t have a stake in this beyond wanting unambiguous definitions.