Hacker News Reader

Comment by yonz | Hacker News Reader

Nice write up, have you looked at Conflict free replicated relations?

We have been discussing Lamport clocks and CRDTs in the context of building local-first applications in our LocalFirstWeb discord https://lfw.dev.

Causality approximated with temporal proximity is a nice way of putting it. I've been trying to wrap my mind around an append only DAG to represent user actions so that multi account, multiuser and multi device experiences can run offline and get to eventually consist state when synced.

View on HN

I have implemented a JSON-like CRDT using this nice tutorial [1], which is a tree, but never an append-only DAG.

I'm curious how two edges meeting the same vertex will make it difficult to resolve the conflict automatically? Is it that two users will create the same vertex (concurrently) with slightly different attributes, and attribute-merging requires human-in-the-loop?

Of course if the DAG is not append-only, but supports, say, "moving" of edges/branches, it is a totally different problem. Martin has something to say about this [2].

[1] https://www.bartoszsypytkowski.com/operation-based-crdts-jso... [2] https://martin.kleppmann.com/papers/move-op.pdf

> what will happen [if] we pick minimum values of the corresponding vector clock entries? The resulting vector clock will describe a point in (logical) time seen by both emitters. If we'll fold this minimum over all most recent timestamps received from all replicas, what we get is the timestamp that describes the point in time seen by everyone - so called stable timestamp. > > This timestamp serves us as a check point - since we know that all events prior to it have been acknowledged by all replicas.

this is not correct, as there is no reliable definition of "all replicas" -- nothing ensures that all replicas in the system are represented in the accounting for a given entity

> CRDT: Replicated state machines allow for generic fault tolerant systems. It does this by having consensus on append to a command log. But if the commands are commutative, those could be applied in any order. There is subset on optimizations on paxos for concurrent commutative commands, called Generalized Paxos. In the extreme case, if all operations are commutative, then you have this nice situation where you don't need consensus. And replicas can converge on the same state, eventually. These data structures with commutative operations are called CRDT.

My thoughts on how clocks, sync and CRDT are related. Not an authority on the subject, so could be quite wrong.

More at: https://ciju.in/posts/2021-09-on-time-clock-and-ordering-of-...

You might be interested by git-bug and https://github.com/MichaelMure/git-bug/blob/master/doc/model..., which seems to be exactly what you describe. (Disclaimer: author).

Reply on news.ycombinator.com