Seonglae ChoRealtime Collaborative Editing protocol
Conflict-free replicated data type
Same state if changes are the same regardless of order
In distributed computing, a conflict-free replicated data type is a data structure that is replicated across multiple computers in a network, where applications can update all replicas simultaneously and independently without coordination with other replicas.
CRDT Tools
CRDT Algorithms
Introduction
An Interactive Intro to CRDTs | jakelazaroff.com
CRDTs don't have to be all academic papers and math jargon. Learn what CRDTs are and how they work through interactive visualizations and code samples.
https://jakelazaroff.com/words/an-interactive-intro-to-crdts/
Local first Development CRDT
To synchronize without an asymmetric server, the server needs to merge changes without knowing the content. For this, homomorphic encryption is proposed instead of traditional encryption.
- Using the TFHE library, the server performs encrypted numerical operations (addition/multiplication) with a server key generated by the client, and the client decrypts the results to obtain correct sum and multiplication results.
- To apply homomorphic encryption to LWW (Last-Write-Wins) Register CRDT, all branches and iterations must be performed a fixed number of times, and use the
selectoperation with encrypted boolean values for conditional replacement to prevent leaks.
While homomorphic encryption CRDT is theoretically possible, it has fundamental limitations in terms of keys, performance, and space, making it difficult to immediately apply to real local-first apps.
Homomorphically Encrypting CRDTs | jakelazaroff.com
Homomorphic encryption allows a computer to run programs on encrypted data. Learn how homomorphic encryption works through interactive examples, build a homomorphically encrypted CRDT and see whether it has promise for local-first software.
https://jakelazaroff.com/words/homomorphically-encrypted-crdts/
Implementation
Building a BFT JSON CRDT
Table of Contents How CRDTs differ from traditional databases When should we use strong eventual consistency over linearizability? Adding Byzantine Fault Tolerance for free (almost) Hashes as IDs and Signed Message Digests Eager Reliable Causal Broadcast and Retries Future directions for CRDTs Acknowledgements CRDTs are a family of data structures that are designed to be replicated across multiple computers without needing to worry about conflicts when people write data to the same place.
https://jzhao.xyz/posts/bft-json-crdt
GNU ELPA - crdt
To install this package from Emacs, use package-install or list-packages.
https://elpa.gnu.org/packages/crdt.html