HackerPapers

arXiv:2004.00107cs.NI

Merkle-CRDTs: Merkle-DAGs meet CRDTs

Hector Sanjuan, Samuli Poyhtari, Pedro Teixeira, Ioannis Psaras

Abstract

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.

arXiv comments
9 pages, 0 figures
Journal reference
DOI
Subjects
cs.NINetworking and Internet Architecture

On Hacker News

Linked by 4 identifiable commenters in 6 comments across 5 threads, from Apr 2020 to Mar 2024. Found in 1 HN submission from Feb 2023 to Feb 2023. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. Prolly Trees 1 comment

    • 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…

      iamwilView on HNParent context

  2. Merkle-CRDTs: Merkle-Dags Meet CRDTs 1 comment
  3. Making CRDTs Byzantine Fault Tolerant [pdf] 1 comment

    • 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…

      hecturchiView on HNParent context

  4. CRDT resources 1 comment

    • 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!

      hecturchiView on HNParent context

  5. OrbitDB: Peer-to-peer databases for the decentralized web 2 comments

    • > 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…

      haadcodeView on HNParent context

    • Posted this in another reply above, but give this a read: "Merkle CRDTs" (https://arxiv.org/abs/2004.00107).

      haadcodeView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.