Hacker News Reader

Comment by samsquire | Hacker News Reader

Does anyone understand merkle clock CRDTs?

How do you handle conflicts where two concurrent events occur at the same time? Who wins? I know timestamps are not reliable but I want last write wins behaviour and seamless merge. The paper leaves data layer conflict resolution to the reader. It does suggest sorting by CID. I added a timestamp field for conflict resolution.

After reading Merkle-DAGs meet CRDTs whitepaper I took a go to implement a MerkleClock. It's incomplete. I need to maintain the partial order of "occurs before".

https://github.com/samsquire/merkle-crdt

I also implemented part of the YATA algorithm yesterday. So I think I could merge the plain text merging functionality of that with the Merkle CRDT.

https://github.com/samsquire/yata

View on HN

In https://github.com/ipfs/go-ds-crdt, every node in the Merkle DAG has a "Priority" field. When adding a new head, this is set to (maximum of the priorities of the children)+1.

Thus, this priority represents the current depth (or height) of the DAG at each node. It is sort of a timestamp and you could use a timestamp, or whatever helps you sort. In the case of concurrent writes, the write with highest priority wins. If we have concurrent writes of same priority, then things are sorted by CID.

The idea here is that in general, a node that is lagging behind or not syncing would have a dag with less depth, therefore its writes would have less priority when they conflict with writes from others that have built deeper DAGs. But this is after all an implementation choice, and the fact that a DAG is deeper does not mean that the last write on a key happened "later".

Thank you for answering this.

I thought of using user indexes by order of connection or user last active time but if you're not worried of the security implications of wall clock and time skew.

Hyperhyperspace project has a previous field on the CRDT operations and can issue undo events to reverse operations.

I suspect you could have a time validator service that is a node that issues revocations if times are in the future. It wouldn't be on the read or write path and it's more to validate that times aren't in the future.

I thought of using Myers algorithm for seamless merging of concurrent updates as this would allow similar strings to remain.

I was interested so I implemented diff3 at HTTPS://GitHub.com/samsquire/text-diff

It doesn't handle conflicts at this time. If the text can be automerged it shall be.

Reply on news.ycombinator.com