We study Merkle-DAGs as a transport and persistence layer for Conflict-Free Replicated Data Types (CRDTs), coining the term Merkle-CRDTs and providing an overview of the different concepts, properties, advantages and limitations involved. We show how Merkle-DAGs can act as logical clocks giving Merkle-CRDTs the potential to greatly simplify the design and implementation of convergent data types in systems with weak messaging layer guarantees and a very large number of replicas. Merkle-CRDTs can leverage highly scalable distributed technologies like DHTs and PubSub algorithms running underneath to take advantage of the security and de-duplication properties of content-addressing. Examples of such content-oriented systems could include peer-to-peer content exchange and synchronisation applications between opportunistically connected mobile devices, IoT devices or user applications running in a web browser.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
Curious: What do you need something like that for? It sounds like some kind of synced backup of a dataset represented by files on S3?
With what you describe, it kinda sounds like a Merkle-DAG CRDT. https://arxiv.org/pdf/2004.00107.pdf
The paper describes a Merkle-DAG that can sync two copies together, because it's also a CRDT. I don't think it's exactly what you want, but I think if you're building an implementation, it gives you the core ideas of what you're looking for.
I also detail Merkle-DAGs in my search.
https://interjectedfuture.com/crdts-turned-inside-out/
If you're looking for something off-the-shelf, I haven't looked for implementations in the wild, so I can't make recommendations.
The idea of DAG-embedded CRDTs is far from new and was introduced here:
https://arxiv.org/abs/2004.00107 (I'm among the authors)
Unfortunately, the verification that the author proposes (not accepting new updates until the dag below is verified) will need a lot of caveats for real world usage.
Currently we use these CRDTs for a key value database of 40M+ keys in a deployment of ipfs-cluster, which uses https://github.com/ipfs/go-ds-crdt .
> Last-Writer-Wins is a conflict resolution strategy that can be used by any kind of data type that needs conflicts resolved, CRDTs included. Unfortunately it's not a very good one: even if you use vector clocks instead of wall clocks, it doesn't give you much stronger guarantees than determinism. That is, given two concurrent writes, the winner is essentially arbitrary. LWW is a merge strategy of last resort; if that's the only thing your CRDT system offers, I'm not sure it's really fair to call it a CRDT system.
Can't reply to the comment below, so replying here.
I believe what markhenderson was trying to say is that in OrbitDB, the default merge strategy for concurrent…
Read the full comment
operations is LWW.
The comment above is conflating a lot of things here. 1) determinism is exactly the guarantee one needs for CRDTs, and I'd argue generally is a good thing in distributed system but 2) adding vector clocks (OrbitDB uses Lamport clocks, or Merkle Clocks [1], by default), nor wall clocks, have nothing to do with determinism and in fact there's a good reason to not use vector clocks by default: they grow unbounded in a system where users (=IDs) are not known. In my experience, LWW is a good baseline merge strategy.
I don't think it's at all correct to say that "the winner is essentially arbitrary" because it's not. The "last" in LWW can be determined based on any number of facts. For example "in case of concurrent operations, always take the one that is written by the ID of the user's mobile device", or "in case of concurrent operations, always take the one that <your preferred time/ordering service> says should come first". It'd be more correct say "the winner is based on the logical time ordering function, which may not be chronological, real world time order".
As for the last comment, I'm pretty sure it's a CRDT system :) Want to elaborate your reasoning why you think it's not a CRDT?
[1] "Merkle-CRDTs: Merkle-DAGs meet CRDTs" - https://arxiv.org/abs/2004.00107
Hehe, or even writing a paper!
https://arxiv.org/abs/2004.00107#
The link takes you to our Merkle-CRDTs paper, which includes a nice intro to CRDTs in general, so no prior knowledge needed!
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
As AI agents powered by Large Language Models (LLMs) become increasingly versatile and capable of addressing a broad spectrum of tasks, ensuring their security has become a critical challenge.