Jens Finkhäuser
@andre actually, @alcinnz worked on an earlier version of the CRDT! Things have evolved since then, though.
The hard part, as he pointed out, is the ordering. Lamport timestamps work - they're logical clocks, where each edit happens one unit after the other, but the units have no real relationship to wall time.
The problem is: how do distributed nodes agree on what is "one unit" and "after?"
Lamport suggested that every node simply keeps its own timestamp, and every edit happens at plus one..
Jens Finkhäuser
@andre @alcinnz ... the actual order of events rather than a logical order, kind of.
This is relying on the fact that siblings nodes in the DAG that share a common ancestor must have synchronized state in order to be able to share an ancestor. And so within each generation you can argue that each node counting monotonically can be considered synchronized from that time point where the ancestor was received.
I wrote this up in a lot more detail: https://interpeer.org/blog/2024/01/comparing-vessel-to-a-merkle-dag/
(First of several posts)
Jens Finkhäuser
@andre @alcinnz ... if you just put a sequence of edits into those chunks, all edits in one precede all edits in another, logically speaking. That's a lot less per-edit overhead, so less stuff to synchronize!
Unfortunately, it also loses enough precision to be potentially bothersome, so I devised a way to do better.
You can combine the logical, DAG-based ordering with a strictly monotonic wall clock per node. The nodes then attach a monotonic timestamp to each edit. It allows merging based...
Jens Finkhäuser
@andre @alcinnz ... the tree, which is useful, but that means updating a partial tree for each edit - the overhead grows O(log(n)).
What we've done is two tiers: on the one hand, vessel is a container - it doesn't have anything to do with CRDTs as such. But it has a different system for ordering chunks of data, which is sufficiently similar to a Merkle tree to work as a logical clock. More specifically, both are DAGs, and it's the DAG properties that make them work that way.
Which means...
Jens Finkhäuser
@andre @alcinnz ... relative to the previous one. To get the entire clock state, you have to synchronize the clocks of all the nodes, and take the most recent timestamp (TL;DR). Vector clocks are a generalization of the concept.
The problem here is that you kind of have to know all the participants in the CRDT and keep a timestamp for each.
A different type of logical clock uses a Merkle tree of edit "events". This works, but has other issues. They sort the most recent edit to the root of...
GNU social JP is a social network, courtesy of GNU social JP管理人. It runs on GNU social, version 2.0.2-dev, available under the GNU Affero General Public License.
All GNU social JP content and data are available under the Creative Commons Attribution 3.0 license.