[Main website]

tech/CRDT

https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

TODO check if they can be used with AST for synchronizing them after some change

They are data-structures that can be maintained in synchronization between different distributed systems:

  • allows for casual consistency through repairs
  • fast to use

[1]M. Letia, N. Preguiça, e M. Shapiro, «Consistency without concurrency control in large, dynamic systems», ACM SIGOPS Operating Systems Review, vol. 44, n. 2, pag. 29, apr. 2010, doi: 10.1145/1773912.1773921.

  • Treedoc is an ordered set
  • it can store text and paragraphs, and the order is the position of the text inside a document
  • MAYBE flat document, not hierarchical tree
  • it is CRDT: commutative, replicated, data-structure
  • supports insert and delete of text at position
  • sometime it needs garbage collection
  • garbage collection can be replicated/distribuited
  • rebalance no: if done no new insert can be accepted and all nodes must agree, so it is not anymore 100% distribuited

https://www.tiny.cloud/blog/real-time-collaboration-ot-vs-crdt/

  • CRDT semantic is not very high-level and merges can be not so useful
  • OT requires a central server, but merge semantic is more powerfull
  • https://news.ycombinator.com/item?id=18191867 it seems that OT works very well in practice because they can compress many local and meaningfull operations on adiacent text. They seems heavy on paper (assuming random transformation), but good in practice.

TODO PeerPad distributed CRDT data structures https://peerpad.net/

PeerPad is a collaborative real-time editor that works on the decentralised web, built on top of IPFS. It uses no second or third-party: all participating nodes talk directly to each other without a central service. PeerPad is open-source and built by Protocol Labs and the IPFS community.

A Conflict-free Replicated Data Type (CRDT) offers ‘Strong Eventual Consistency’: a flavour of eventual consistency that ensures conflicts can be merged automatically to produce a value that is guaranteed to be correct/consistent.

Two objects can be either equal, have hierarchy (one descends the other) or are pairs; the latter signifies a branch/divergence/conflict. From the intrinsic state of the two pairs, we can determine a new descendant object which is the result of the merge.