# Algorithms ## Replication Model Collabs implements hybrid op-based/state-based [Conflict-free Replicated Data Types (CRDTs)](https://crdt.tech/). This means that you can share updates using both _messages_ (op-based CRDT usage) and _saved states_ (state-based CRDT usage), as described in [Updates and Sync](../advanced/updates.html). In a Collab implementation, [send](../api/collabs/classes/Collab.html#send) and [receive](../api/collabs/classes/Collab.html#receive) correspond to op-based CRDT usage, while [save](../api/collabs/classes/Collab.html#save) and [load](../api/collabs/classes/Collab.html#load) correspond to state-based usage. ## Built-in Collabs Our [built-in Collabs](../guide/built_in_collabs.html) use CRDT algorithms from (or inspired by) various sources, shown in the table below. | **Collab** | **Algorithm** | **References** | **Comments** | | ------------------------------------------------------------------------------------------------------------------------------------ | -------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | [CBoolean](../api/collabs/classes/CBoolean.html) | Enable-Wins Flag, or Disable-Wins Flag with option `{ winner: false }` | [Pure Operation-based Replicated Data Types](http://arxiv.org/abs/1710.04469v1), Carlos Baquero, Paulo Sérgio Almeida, and Ali Shoker | | | [CCounter](../api/collabs/classes/CCounter.html) | State-based PN-Counter | [A Comprehensive Study of Convergent and Commutative Replicated Data Types](https://hal.inria.fr/inria-00555588/document/), Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski | Op-based messages work similarly to the delta-CRDT Counter from [Delta State Replicated Data Types](http://dx.doi.org/10.1016/j.jpdc.2017.08.003), Paulo Sérgio Almeida, Ali Shoker, and Carlos Baquero. | | [CLazyMap](../api/collabs/classes/CLazyMap.html) | Riak Map without deletions | [Riak Data Types: Maps](https://docs.riak.com/riak/kv/2.2.3/developing/data-types/maps.1.html). Similar CRDT-valued maps appear in [Logic and Lattices for Distributed Programming](https://doi.org/10.1145/2391229.2391230), Neil Conway, William R. Marczak, Peter Alvaro, Joseph M. Hellerstein, and David Maier; [LVars: Lattice-based Data Structures for Deterministic Parallelism](https://doi.org/10.1145/2502323.2502326), Lindsey Kuper and Ryan R. Newton; and [Composition of State-based CRDTs](http://haslab.uminho.pt/cbm/files/crdtcompositionreport.pdf), Carlos Baquero, Paulo Sérgio Almeida, Alcino Cunha and Carla Ferreira. | Like the Riak Map, there is a single value CRDT per key that implicitly always exists, all operations on that value are merged, and a key is present if and only if its value CRDT is in a nontrivial state (determined by [Collab.canGC](../api/collabs/classes/Collab.html#canGC)). Unlike the Riak map, we do not allow delete-key operations, which in Riak would perform an observed-reset operation on the value. | | [CList](../api/collabs/classes/CList.html) | List-with-Move | [Moving Elements in List CRDTs](https://doi.org/10.1145/3380787.3393677), Martin Kleppmann | In addition to position, the register has an `isPresent` field, used for archive/restore. Also, we use our [CSet](../api/collabs/classes/CSet.html) instead of an Add-Wins Set. | | [CMap](../api/collabs/classes/CMap.html) | [CValueMap](../api/collabs/classes/CValueMap.html) with values from a [CSet](../api/collabs/classes/CSet.html) | | Inspired by how [Yjs's Y.Map](https://docs.yjs.dev/api/shared-types/y.map) handles values that are themselves shared types. | | [CMultiValueMap](../api/crdts/classes/CMultiValueMap.html) | Multi-Value Register per key | [A Comprehensive Study of Convergent and Commutative Replicated Data Types](https://hal.inria.fr/inria-00555588/document/), Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski | A key is present whenever its Multi-Value Register has nonzero conflicting values; the [delete](../api/crdts/classes/CMultiValueMap.html#delete) operation just clears the (causally prior) conflicting values. For state-based merging of a saved state, we delete conflicts based on a vector clock instead of tombstones, following [An Optimized Conflict-free Replicated Set](https://hal.inria.fr/file/index/docid/738680/filename/RR-8083.pdf), Annette Bieniusa, Marek Zawirski, Nuno Preguiça, Marc Shapiro, Carlos Baquero, Valter Balegas, and Sérgio Duarte. | | [CObject](../api/collabs/classes/CObject.html) | Similar to CLazyMap, but with a fixed set of keys (the child names). | See CLazyMap references. | We have not seen an identical "CRDT object" idea in the literature, but the idea and semantics are obvious (multiple independent CRDTs side-by-side, keyed by name). | | [CTotalOrder](../api/crdts/classes/CTotalOrder.html) and [LocalList](../api/collabs/classes/LocalList.html) (used in all list types) | Tree-Fugue List CRDT | [The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing](https://arxiv.org/abs/2305.00583), Matthew Weidner, Joseph Gentle, and Martin Kleppmann. | Blog post: [Fugue: A Basic List CRDT](https://mattweidner.com/2022/10/21/basic-list-crdt.html). As an optimization, we use "waypoints" as described in [CTotalOrder's doc header](../api/crdts/classes/CTotalOrder.html); those are inspired by [Yjs's items](https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/). | | [CRichText](../api/collabs/classes/CRichText.html) | Peritext | [Peritext: A CRDT for Collaborative Rich Text Editing](https://doi.org/10.1145/3555644), Geoffrey Litt, Sarah Lim, Martin Kleppmann, and Peter van Hardenberg. | The semantics are substantially similar to Peritext's, but we use somewhat different internal representations. For example, we store formatting span starts and ends in a separate [LocalList](../api/collabs/classes/LocalList.html) instead of inline with the text (which is stored in a [CValueList](../api/collabs/classes/CValueList.html)). | | [CSet](../api/collabs/classes/CSet.html) | Unique Set of CRDTs | [Designing Data Structures for Collaborative Apps](https://mattweidner.com/2022/02/10/collaborative-data-design.html), Matthew Weidner. The Unique Set (U-Set) with non-CRDT values is from [A Comprehensive Study of Convergent and Commutative Replicated Data Types](https://hal.inria.fr/inria-00555588/document/), Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. | If a value is deleted concurrently to an operation on that value, the delete "wins" and the operation is ignored. That "deleting" semantics comes from [Yjs's Y.Array](https://docs.yjs.dev/api/shared-types/y.map) shared type. | | [CValueMap](../api/collabs/classes/CValueMap.html) | [Aggregator](../api/collabs/interfaces/Aggregator.html) of a Multi-Value Register per value | [Eventually Consistent Register Revisited](http://dx.doi.org/10.1145/2911151.2911157), Marek Zawirski, Carlos Baquero, Annette Bieniusa, Nuno Preguiça, and Marc Shapiro | The default aggregator returns the conflicting value with least [senderID](../api/collabs/interfaces/MultiValueMapItem.html#senderID). That is similar in spirit to a Last-Writer-Wins (LWW) Map - pick an arbitrary causally-maximal value - but it does not use an actual timestamp. | | [CValueSet](../api/collabs/classes/CValueSet.html) | Add-Wins Set / Observed-Remove Set | [An Optimized Conflict-free Replicated Set](https://hal.inria.fr/file/index/docid/738680/filename/RR-8083.pdf), Annette Bieniusa, Marek Zawirski, Nuno Preguiça, Marc Shapiro, Carlos Baquero, Valter Balegas, and Sérgio Duarte | | | [CVar](../api/collabs/classes/CVar.html) | [Aggregator](../api/collabs/interfaces/Aggregator.html) of a Multi-Value Register | [Eventually Consistent Register Revisited](http://dx.doi.org/10.1145/2911151.2911157), Marek Zawirski, Carlos Baquero, Annette Bieniusa, Nuno Preguiça, and Marc Shapiro | The default aggregator returns the conflicting value with least [senderID](../api/collabs/interfaces/MultiValueMapItem.html#senderID). That is similar in spirit to a Last-Writer-Wins (LWW) Register - pick an arbitrary causally-maximal value - but it does not use an actual timestamp. |