CRDTs and the Quest for Distributed Consistency

InfoQ Dev Summit Boston, a two-day conference of actionable advice from senior software developers hosted by InfoQ, will take place on June 24-25, 2024 Boston, Massachusetts.

Deep-dive into 20+ talks from senior software developers over 2 days with parallel breakout sessions. Clarify your immediate dev priorities and get practical advice to make development decisions easier and less risky.

--------------------------------------------------------------------------------------------------------------------------------------

Martin Kleppmann explores how to ensure data consistency in distributed systems, especially in systems that don't have an authoritative leader. He explains how to sync data between a phone and a laptop without sending it via a remote server. He also explores algorithms that allow several people to collaborate on a shared document, communicating via a peer-to-peer network.

#SoftwareArchitecture #DistributedSystems #CRDT #Consistency #InfoQ #QCon #QConLondon

[MarioGonzalez-lojk]

Excellent speaker. No snarkiness, no cheesy clip-art. Slowly eases more deeply into the subject, in a way where you never feel like they skipped a step and are now lost

[uybabayun]

That book is just awesome! Highly recommended if anyone is interested...

[ajaymenon]

This has to be the most concise talk I've seen in a long time.
Probably hit a new benchmark for how crisp talks can be without being overbearing.

[bdwizard]

Superb speaker! An excellent author as well.

[xianggu]

My understanding of the automerge algorithm:
1. Treat the whole document as a list of characters and give each character a unique identifier that is totally ordered (think: timestamp each event with (event's logical clock, process id) gives a total order among all events)
2. Record each edit and send them to the other concurrently editing user (e.g. Msg={insert character "a" with id 4a after existing character 2a}).
3. Each user applies the all the local and incoming/external edits. When a conflict arises, reply on the total order to make a "sensible" resolution (e.g. in case of inserting, "smaller" inserts takes precedence over "larger" inserts, so that both users end up in the same string).

It seems to me this algorithm is a special case of CRDT (on the `insert` method of a `list` date structure so that concurrent `insert`s are ensured identical state on the `list` on both replicas). In general, we can do this to any method on any data structure, and we want the implementations to be *commutative*, which conveniently ensures "ending up in the same state after applying all operations, even if ops are applied in different order".

[KalyanSP]

This dude is a freaking legend. The book is phenomenal. Complex topics explained so well

[snowy]

Such a breath of fresh air after spending tons of time watching marketing-related talks about "new technology XYZ". Thanks! That's awesome!

[ShortGiant]

What a great talk! Such an interesting topic explained in an easy to understand manner. Also, great slides!

[franciscolopezsancho]

What a gem the content, and the delivery. Enlightening. Thanks!!

[DanPiponi]

The punch line is 40:28 to 42:28. Very clever.

[paveltyk]

He talks faster than I can think! Great explanation. The book is also brilliant. Had to read it multiple times to get in all details :)

[TJ-hsqm]

I can see how language models could be used to resolve conflicts in a "natural way". "Hi mom dad!" would become "Hey mom and dad!" or in "Hey everyone folks" it would understand the redundancy and automatically suggest sensibel alternatives.

[jehan]

thanks for explaining things clearly! Espeically "push is the JS operation for updating an array" (around 28:00). Makes it easier for people unfamiliar with a particular language to understand!

[draakisback]

Pretty nice rundown of crdts. I've been using them in non document based systems. For example, an orderbook. In an ordebook, you have very specific operations; and they map very nicely onto the crdt ops and types. My system is also running a hybrid consensus/collaberative algorithm because there are cases where the book wants to reject certain changes but it scales incredibly well.

[ibgib]

I've have greatly enjoyed this speaker's previous talks on append only logs and others. This talk was fabulous in that it was thought provoking, charismatic and he's out their on stage doin his thing... However I have a few issues regarding many points claimed. Probably the biggest point is CRDTs vs consensus. If one is talking about _bitcoin_ and its hard-coded consensus, then yes, they are only superficially similar. But consensus in general is an algorithm for choosing the next state (not just the next block). The last section about automerge basically delineates their naive (meant literally not pejoratively) conflict resolution for edge cases. But their algorithm essentially is another hard coded consensus with implied limitations on state shapes and the transformations allowed as a tradeoff for the mathematical backing of the expected deterministic outcomes.

Still a very good talk that is helping me get where I need to go, so a big Thank You!

[fsmctlr]

Excellent talk from an excellent speaker.

[sobanya_]

Is there any kind of immutable api for Automerge?

[kokizzu]

what happened if current data is both A=1
User1 delete/expire a record with key A
and User2 update/upsert a record with key A to value 2

[lidu]

The comments from 10:00 to 12:00 about operational transformation (OT) are out of date. The correctness problem of OT was solved around 2006, which was published in a 2010 JCSCW paper by Li&Li. A family of OT algorithms, called ABT*, were developed by Shao & Li from 2009 to 2011. More details about this line of work are provided in a short essay written in 2011, which can be found on my LinkedIn profile.

[bryanhaakman]

At 32:42: how about using "time" as a way to decide which change to pick? So the change that was made later gets preferred?