Skip to content
The methodOpen data
Back to the collection

Delta State Replicated Data Types

Paulo Sérgio Almeida, Ali Shoker, Carlos Baquero

2016 · arXiv

Distributed systemsStatistics & probabilityAlgorithms
Read the paper
HN score
0
Mentions
3
Readers
3
Months
3
What’s in a score?

From the abstract

CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs ensure convergence through disseminating the entire state, that may be large, and merging it to other replicas; whereas operation-based CRDTs disseminate operations (i.e., small states) assuming an exactly-once reliable dissemination layer. We introduce Delta State Conflict-Free Replicated Data Types ($δ$-CRDTs) that can achieve the best of both worlds: small messages with an incremental nature, as in operation-based CRDTs, disseminated over unreliable communication channels, as in traditional state-based CRDTs. This is achieved by defining delta mutators to return a delta-state, typically with a much smaller size than the full state, that to be joined with both local and remote states. We introduce the $δ$-CRDT framework, and we explain it through establishing a correspondence to current state-based CRDTs. In addition, we present an anti-entropy algorithm for eventual convergence, and another one that ensures causal consistency. Finally, we introduce several $δ$-CRDT specifications of both well-known replicated datatypes and novel datatypes, including a generic map composition.

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

3 selected excerpts · 3 total mentions

linkdd
Neutral mention · rule
Last-Write-Win CRDTs are nice, but I wish the article talked about where CRDT really shine, which is when the state truly converge in a non-destructive way, for example: 1) Counters While not really useful, they demonstrate this well: - mutations are +n and -n - their order do not matter - converging the state is a matter of applying the operations of remote peers locally 2) Append-only data structures Useful for accounting, or replication of time-series/logs with no master/slave relationship between nodes (where writes would be accepted only on a "master" node). - the only mutation is "append" - converging the state is applying the peers operations then sorting…
Read the full comment
by timestamp EDIT: add more 3) Multi Value registers (and maps) Similar to Last-Write-Win registers (and maps), but all writes are kept, the value becomes a set of concurrent values. 4) Many more... Each is useful for specific use cases. And since not everybody is making collaborative tools, but many are working on distributed systems, I think it's worth it to mention this. On another note, the article talks about state based CRDTs, where you need to share the whole state. In the examples I gave above, they are operation based CRDTs, where you need to share the operations done on the state and recompute it when needed. For example, in the Elixir ecosystem, we have Horde ( https://hexdocs.pm/horde/readme.html ) which allows distributing a worker pool over multiple nodes, it's backed by DeltaCrdt ( https://hexdocs.pm/delta_crdt/DeltaCrdt.html ). Delta-CRDTs are an optimization over state based CRDTs where you share state diffs instead of the whole state (described in this paper: https://arxiv.org/pdf/1603.01529 ).
Original comment An Interactive Intro to CRDTs
rklaehn
Neutral mention · rule
Yes, there is a lot of awesome stuff that just works. SSB, the entire DAT/hypercore community, tools like syncthing that just do one thing well. I like the SSB approach of just embracing subjectivity. I was quite amazed when discovering all this at dtn.is (Before I only knew the IPFS community). But I feel there is still something missing for very wide spread adoption. What we are trying to do with TLFS is to combine - a CRDT with strict schema ( Adapted from https://arxiv.org/abs/1603.01529 ) - a built in way to do schema evolution ( Adapted from https://www.inkandswitch.com/cambria/ ) - local first / p2p deployment and operation even for native apps, based on…
Read the full comment
https://github.com/libp2p/rust-libp2p , faciliated by https://github.com/cloudpeers/x We're not nearly there yet, but ideally it should be so easy to write small collaborative apps that it is a good option even if you don't care about the idealistic motivations for decentralized apps.
Original comment Locutus: A platform for building decentralized apps, from the creator of Freenet
iamaleksey
Neutral mention · rule
Except they are. Catalogued as δ-CRDT, under Lexicographic Counter in https://arxiv.org/pdf/1603.01529.pdf edit: Although to be fair that blog post is ancient and covers Cassandra 2.0, now no longer supported. Counters were rewritten in Cassandra 2.1.
Original comment Databases and Distributed Deadlocks: A FAQ

Keep following the thread.

More in Distributed systems

More from the same topics.