We're building a multiplayer IDE [1] but for docs/planning where docs needs to be trees/graphs (to support outlining, refs, transclusions and so on)
We can't just merge any type of operation by replaying unconditionally, because that can cause tree cycles for example. Like the linked list certain operations can be valid locally for an offline client, but not globally in the converged order.
Our sync engine distinguishes between different types of operations: unconditional operations and guarded operations.
Unconditional operations can't violate structural/data-model invariants. For example SetCompleted(task_guid, true). Simple last-writer-wins.
Guarded operations can mutate topology, like InsertMove(node_guid, parent_guid, after_guid). These are checked against the current state, not the state when they were created. During replay we first revert optimistic local operations and replay the incoming canonical operations in order. The mutator function for each operation validates the current state before applying it and if it would violate a condition (for example by creating a cycle because another client made another move in the meantime) it is deterministically rejected. In our case we also have an authoritative server so we can also use the same guarded operations for conditions beyond data structure, like permissions, so the AddUser(workspace_guid, user_guid) mutator function can check permissions state first for example.
That's right, they become part of the replay and rejected using the same path, otherwise things like cycles might still happen. Rejected ops do stay part of the log though, so there's always ways to build time travel/version history or conflict UIs on top when needed.
> Is it a good enough idea to sync MMO game clients and servers?
After 15 years in the trenches on this stuff, no I don’t think so. Some operations need a clearly defined order for correctness. For example, financial transactions or items moving between inventories. CRDTs don’t provide this.
CRDTs are great when it makes sense for a local peer to own changes. Like Git. I think automerge and friends would make for excellent tools for making virtual worlds. For example, the recent work to integrate automerge into the Godot game engine.
> That’s well outside Automerge’s comfort zone, and this note is about what happens out there.
I am once again begging people who generate notes like this with LLMs to review the output critically. The examples above are wholly meaningless sentences, but the article contains enormous redundancy and is not easy to read. The actual point, that merging requires context, is not stated explicitly until more than half way through the article and does not need to be restated in 8 different ways.
I'm having a hard time believing
(a) that you think Wave failed because of the tech stack, and also
(b) that you think when a product launch fails, all products that conceptualize the market/problem in that category will also fail.
I'm hesitating to post this, but really, if that's not what you're saying, it feels like trying to make a zinger has overwhelmed your actual point.
> Martin Kleppmann, Vincent Liu, Owen Lynch, and their collaborators are tackling the problem head-on in Coln, a mergeable database with an expressive language for schemas, queries, and migrations. In Coln, you can declare constraints on your data — “this is a doubly-linked list”, say — and it takes a refreshingly strict line on violations: if merging would break a constraint, the merge is simply refused
Isn't that similar to the "theory of patches", like implemented in Pijul?
We're building a multiplayer IDE [1] but for docs/planning where docs needs to be trees/graphs (to support outlining, refs, transclusions and so on)
We can't just merge any type of operation by replaying unconditionally, because that can cause tree cycles for example. Like the linked list certain operations can be valid locally for an offline client, but not globally in the converged order.
Our sync engine distinguishes between different types of operations: unconditional operations and guarded operations.
Unconditional operations can't violate structural/data-model invariants. For example SetCompleted(task_guid, true). Simple last-writer-wins.
Guarded operations can mutate topology, like InsertMove(node_guid, parent_guid, after_guid). These are checked against the current state, not the state when they were created. During replay we first revert optimistic local operations and replay the incoming canonical operations in order. The mutator function for each operation validates the current state before applying it and if it would violate a condition (for example by creating a cycle because another client made another move in the meantime) it is deterministically rejected. In our case we also have an authoritative server so we can also use the same guarded operations for conditions beyond data structure, like permissions, so the AddUser(workspace_guid, user_guid) mutator function can check permissions state first for example.
[1] https://thymer.com
So what happens with optimistic local operations that become invalid after replay of canonical operations? Are they just thrown away as well?
That's right, they become part of the replay and rejected using the same path, otherwise things like cycles might still happen. Rejected ops do stay part of the log though, so there's always ways to build time travel/version history or conflict UIs on top when needed.
Relevant paper on lattice types (BloomL): https://dsf.berkeley.edu/papers/UCB-lattice-tr.pdf
In addition to this, you’ll need a causal register (per-key merkle clock) to order concurrent edits, rather than drop one.
Lastly, you’re likely to need a Pijul style VCS to handle semantic merges.
This is apparently based on Automerge.[1] It sounds like a really good idea. Is it a good enough idea to sync MMO game clients and servers?
Paper from 2012, last Automerge site update in 2025. Why isn't this everywhere?
[1] https://automerge.org/
> Is it a good enough idea to sync MMO game clients and servers?
After 15 years in the trenches on this stuff, no I don’t think so. Some operations need a clearly defined order for correctness. For example, financial transactions or items moving between inventories. CRDTs don’t provide this.
CRDTs are great when it makes sense for a local peer to own changes. Like Git. I think automerge and friends would make for excellent tools for making virtual worlds. For example, the recent work to integrate automerge into the Godot game engine.
Thank you for all your work on CRDTs, I think dt is still the coolest leap I've seen in software and frankly in thinking about the universe.
They say in the article: the correct resolution of a merge depends on the context. Automatic resolution may introduce bugs!
> this is an acknowledgment, not a victory lap
> That’s well outside Automerge’s comfort zone, and this note is about what happens out there.
I am once again begging people who generate notes like this with LLMs to review the output critically. The examples above are wholly meaningless sentences, but the article contains enormous redundancy and is not easy to read. The actual point, that merging requires context, is not stated explicitly until more than half way through the article and does not need to be restated in 8 different ways.
> every object, class, and method — is an Automerge document
Sounds an awful lot like the Google Wave experiment but on steroids. And we know how it ended.
I'm having a hard time believing (a) that you think Wave failed because of the tech stack, and also (b) that you think when a product launch fails, all products that conceptualize the market/problem in that category will also fail.
I'm hesitating to post this, but really, if that's not what you're saying, it feels like trying to make a zinger has overwhelmed your actual point.
> Martin Kleppmann, Vincent Liu, Owen Lynch, and their collaborators are tackling the problem head-on in Coln, a mergeable database with an expressive language for schemas, queries, and migrations. In Coln, you can declare constraints on your data — “this is a doubly-linked list”, say — and it takes a refreshingly strict line on violations: if merging would break a constraint, the merge is simply refused
Isn't that similar to the "theory of patches", like implemented in Pijul?