# Collabs: Composable Collaborative Data Structures

Matthew Weidner  Carnegie Mellon UniversityUnited States
<EMAIL_ADDRESS>,  Heather Miller  Carnegie Mellon UniversityUnited
States<EMAIL_ADDRESS>,  Huairui Qi  Carnegie Mellon
UniversityUnited States<EMAIL_ADDRESS>,  Maxime Kjaer  EPFL
ICSwitzerland<EMAIL_ADDRESS>,  Ria Pradeep  Carnegie Mellon
UniversityUnited States<EMAIL_ADDRESS>,  Benito Geordie  Rice
UniversityUnited States<EMAIL_ADDRESS>and  Christopher Meiklejohn  Carnegie
Mellon UniversityUnited States<EMAIL_ADDRESS>
###### Abstract.

Replicated data types (RDTs), such as Conflict-free Replicated Data Types
(CRDTs), provide an abstraction for reasoning about replication and
consistency in distributed systems. To make them as useful as ordinary, local
data structures, RDTs need to be both _modular_ and _composable_ , so that
programmers can create new app-specific RDTs by composing existing ones.
However, no existing RDT libraries combine these properties; either they use
monolithic architectures that rule out new RDTs or they do not support
composition techniques. Thus in practice, programmers are forced to store
replicated data in generic formats like JSON, and they cannot make use of new
RDT algorithms that libraries are slow to implement.

In this work, we introduce the _Collab (collaborative data structure)_ , a
novel abstraction for modular and composable RDTs. We also describe the
_collabs library_ , an open-source111https://github.com/composablesys/collabs
TypeScript library that we built around this abstraction. Our library supports
arbitrary programmer-added RDTs and includes composition techniques that make
them easier to implement. This allows programmers to work at a higher level of
abstraction: custom RDTs for arbitrary concepts in their application, instead
of just a fixed menu of generic RDTs. It also allows programmers to extend the
library with new RDT algorithms as they are published, instead of waiting for
the library to implement them. Our library includes a collection of built-in
op-based CRDT implementations, including several that were not previously
implemented. To demonstrate the library, we built numerous apps on top of it,
including decentralized collaborative apps that can be deployed from a static
web page. Benchmarks show that its CRDTs have performance comparable to state-
of-the-art CRDT libraries for web apps, and that unlike existing libraries, it
can support 100 simultaneous users with low latency in a geo-distributed
collaborative app.

Distributed systems consistency, Conflict-free Replicated Data Types,
TypeScript

††copyright: none††ccs: Software and its engineering Data types and
structures††ccs: Computer systems organization Distributed architectures††ccs:
Theory of computation Distributed algorithms

##  1\. Introduction

A fundamental distributed systems problem is consistency: keeping replicated
data in sync across different devices. It is the central challenge in geo-
replicated databases, consensus protocols, cache coherence, and end-user apps
like real-time collaborative document editors. Different applications require
different consistency guarantees—rules about when and how replicas can become
out of sync—but providing these guarantees is difficult, especially when
programming distributed systems at the level of message-passing.

_Replicated Data Types (RDTs)_ (Burckhardt et al., 2014) provide a higher-
level abstraction for reasoning about replication and consistency. These are
data structures that are replicated on multiple devices and allow each device
to mutate and query the replicated state, while also guaranteeing some level
of consistency. In particular, _Conflict-free Replicated Data Types (CRDTs)_
(Shapiro et al., 2011a; Preguiça et al., 2018) are a class of RDTs that are
highly available, even under network partitions, but that still give
reasonable consistency guarantees. Due to these properties, CRDTs are used in
geo-replicated databases (AntidoteDB, 2019; Basho, 2015; Conway et al., 2012)
and end-user collaborative apps (Kleppmann et al., 2018b, 2019; Nicolaescu et
al., 2016), and many recent works concern algorithms or libraries for CRDTs
(van der Linde et al., 2016; Kleppmann and Beresford, 2017; Kleppmann, 2020b;
Jahns, 2022; contributors, 2022; van der Linde et al., 2017; Jannes et al.,
2021).

Ideally, RDTs would be as easy to use as ordinary, local data structures.
Existing libraries try to make this possible by providing RDT implementations
that have APIs like local data structures but that internally use expert-
written algorithms to ensure consistency. Providing these in a library is
important because even experts find it difficult to write correct algorithms
(e.g., see (Imine et al., 2003)). By implementing RDTs for general-purpose
data types like maps and lists—sometimes including maps and lists whose values
can themselves be RDTs—existing libraries make it possible in principle to
replicate arbitrary apps’ data.

Unfortunately, designing an app around general-purpose RDTs has shortcomings
in practice. First, programmers are forced to store and manipulate all data in
a generic format—essentially JSON—and cannot easily encapsulate app-specific
concepts or use language features like classes and types. This makes it
difficult to manage complex state, e.g., that of a collaborative presentation
editor. Second, when weakly consistent RDTs like CRDTs resolve conflicts
between concurrent operations, they guarantee _some_ consistent result, but it
may not be what programmers or users expect. For example:

Moving slides:

In a collaborative presentation editor, it is natural to store the list of
slides using a list CRDT. But with standard list CRDTs, if one user moves a
slide while another edits it concurrently, then the concurrent edits will be
lost. Kleppmann (2020b) describe a “list-with-move” CRDT as a solution, but no
existing library implements it.

Formatting rich text:

In a collaborative text editor, a simple way to store the text is as a list of
pairs (character, formatting attributes), where the latter is a map CRDT. But
then if one user bolds a range of text while concurrently, another user types
in the middle of the range, then the newly-typed characters will not match the
bold formatting.

Both of these shortcomings could be solved by using app-specific RDTs instead
of general-purpose ones—e.g., a “presentation CRDT” that has a presentation-
specific API and that uses the ideal behavior when moving slides. But existing
libraries either do not permit custom RDTs at all or only permit ones written
from scratch using message-passing. Thus this solution is out of reach for
typical app programmers, unless some library happens to implement an RDT for
their specific application—the case for rich text (Jahns, 2022) but little
else.

In contrast, local data structure libraries do not have these shortcomings.
This is because local data structures are:

Modular:

Each data structure is its own unit, independent of other data structures in
the same library. Thus the library is extensible: programmers are free to add
their own data structures, with arbitrary APIs and implementations.

Composable:

Simple data structures can be composed to create more complex ones. This makes
it easy for app programmers to model their own data (e.g., using classes), and
it also lets complex data structures inherit behavior and correctness
guarantees from their components (e.g., a hash set can internally use a hash
map).

However, no existing RDT libraries combine these properties. Yjs (Jahns, 2022;
Nicolaescu et al., 2016), Automerge (contributors, 2022), and OWebSync (Jannes
et al., 2021) support either composable maps and lists or JSON-formatted data,
but they use monolithic architectures that rule out programmer-added data
structures; ShareDB (Smith and Gentle, 2022) and Fluid Framework (Fluid
Framework, 2022) allow modular custom RDTs but do not support composition
techniques.

###  1.1. Contribution

Our work is the first to support modularity and composition for RDTs,
including op-based CRDTs (Shapiro et al., 2011a). Specifically:

  1. (1)

We introduce an abstraction for modular and composable RDTs that we call a
_Collab_ , short for _collaborative data structure_ , and an API realizing
this abstraction (Section 3).

  2. (2)

We implement an open-source TypeScript library, the _collabs library_, around
the Collab abstraction (Sections 4—5). It includes helpers for using and
implementing Collabs, composition techniques, and a collection of CRDT
implementations. Programmers using the library are free to add their own
Collab implementations and composition techniques.

  3. (3)

As part of the library, we give the first implementations of several CRDTs and
CRDT composition techniques, namely, the semidirect product of CRDTs (Weidner
et al., 2020), list-with-move CRDT (Kleppmann, 2020b), and an optimized
resettable counter (Weidner and Almeida, 2022) (Section 5.3).

  4. (4)

We describe numerous apps that we implemented on top of the library, including
decentralized collaborative apps (Section 6). We also demonstrate how one can
pair collabs with the Matrix federated chat protocol to deploy these
collaborative apps using only a static web page, instead of an expensive
server deployment. This deployment method, plus the relative ease of writing
collabs apps, _democratizes_ collaborative apps, putting their creation and
deployment within reach of individuals and open-source projects instead of
just large companies.

  5. (5)

We benchmark our CRDTs against Yjs (Jahns, 2022; Nicolaescu et al., 2016) and
Automerge (contributors, 2022), two state-of-the-art CRDT libraries for web
apps, and show that it has comparable performance on individual CRDT
benchmarks, plus better performance on an end-to-end test of a geo-distributed
collaborative app with 100 simultaneous users (Section 7).

In more detail, the Collab abstraction is a particular formulation of an RDT
that is meant to look as much as possible like an ordinary, local data
structure from an app programmer’s perspective, while also being modular and
composable. For example, one of our demos implements a rich-text CRDT as a
Collab with the API shown in Figure 2. App programmers mutate and query state
with rich-text-specific method calls. Under the hood, each mutating method
call sends a message to the Collab’s replicas on other devices, causing them
to update their own internal state and emit an event describing the change
(not shown). App programmers use these events to update the GUI.

⬇

1class CRichChar {

2 readonly char: string;

3 getAttribute(attr: string):

4 unknown;

5 setAttribute(attr: string,

6 value: unknown);

7 attributes():

8 Record<string, unknown>;

9}

10

11class CRichText {

12 get(index: number): CRichChar;

13 get length(): number;

14 insert(index: number,

15 char: string,

16 attr: Record<string, unknown>);

17 delete(startIndex: number,

18 count: number);

19 format(index: number,

20 newAttr:

21 Record<string, unknown>

22 );

23}

Figure 1. API for a rich-text CRDT implemented using collabs. unknown is
TypeScript’s top type.

⬇

1class CRichChar

2 extends CObject {

3 readonly char: string;

4 // Immutable, so not a Collab.

5 attributes:

6 LWWCMap<string, unknown>;

7}

8

9class CRichText

10 extends CObject {

11 text: ArchivingMutCList<

12 CRichChar, /*...*/

13 >;

14 sdpStore:

15 SemidirectProductStore</*...*/>;

16}

Figure 2. Design of a compositional implementation for CRichText.

While a rich-text CRDT implementation is not novel on its own (Jahns, 2022),
this example illustrates collabs’s unique combination of modularity and
composability. Modularity allows any programmer is free to implement Collabs
with arbitrary algorithms and APIs. Thus expert programmers can implement CRDT
algorithms like the list-with-move as they are published, instead of waiting
for the library to implement them. More generally, this allows programmers to
work at a higher level of abstraction, namely, custom RDTs for arbitrary
concepts in their application, instead of just a fixed menu of generic types.
For example, a programmer making a collaborative presentation editor could
define Collabs for slide elements, slides, presentations, etc.

The collabs library’s composability means that implementing the rich-text CRDT
was easier than implementing a rich-text CRDT from scratch (e.g., Peritext
(Litt et al., 2021)). Instead of directly sending messages and proving strong
eventual consistency, we used the compositional design in Figure 2. Here
LWWCMap is a built-in CRDT map; ArchivingMutCList is a CRDT collection of
CRDTs; CObject is a class that one can subclass to easily create new Collabs
with Collab instance fields; and SemidirectProductStore implements the
semidirect product of CRDTs (Weidner et al., 2020), which is used here to
enforce the insert-concurrent-to-formatting behavior described above. The
figure omits implementation, but even with the semidirect product (which a
basic implementation could omit), it is much simpler than representing
formatting ranges via markers at both ends as in Yjs (Jahns, 2022; Nicolaescu
et al., 2016) and Peritext (Litt et al., 2021)—an approach that requires
tricky manipulations to ensure strong eventual consistency

We use similar compositional designs to implement many other CRDTs (see
Sections 5.3 and 6.1), including the first implementation of the list-with-
move CRDT (Figure 13)—a CRDT that has been requested in Yjs and Automerge but
would be difficult to add to them222Yjs: https://discuss.yjs.dev/t/moving-
elements-in-lists/92/5, Automerge:
https://github.com/automerge/automerge/issues/263#issuecomment-677563993.. In
general, we expect that even non-expert app programmers can use these
composition techniques to model data in their own apps. Meanwhile, expert
programmers can implement not just new RDT algorithms but even new composition
techniques and provide them as extension libraries.

##  2\. Related Work

Many works investigate aspects of RDTs, including consistency guarantees
(e.g., (Viotti and Vukolić, 2016)), replication models and implementation
techniques (e.g., Operational Transformation (Ressel et al., 1996) and CRDTs
(Shapiro et al., 2011a)), applications (e.g., geo-replicated databases (Basho,
2015) and collaborative apps (Kleppmann et al., 2018b)), and numerous specific
algorithms and libraries. The collabs library’s place among this work is as a
library that is agnostic about consistency guarantees and algorithms, but that
specifically supports message-based replication models like op-based CRDTs
(Section 5) or sequentially consistent RDTs (Section 6.3). Also, as a
TypeScript library, it mainly targets the client side of web apps.

The two most similar existing libraries are Yjs (Jahns, 2022; Nicolaescu et
al., 2016) and Automerge (contributors, 2022). Like collabs’s CRDT library,
these are both TypeScript/JavaScript CRDT libraries that support compositional
data, are intended for collaborative web apps, and are network-agnostic. Yjs
supports nestable map, array, rich text, and XML CRDTs based on the YATA
sequence CRDT algorithm (Nicolaescu et al., 2016), with a focus on performant
collaborative text editing (Jahns, 2020a). Automerge is a persistent CRDT for
JSON-formatted data based on OpSets (Kleppmann et al., 2018a). Unlike collabs,
neither library allows programmer-added CRDTs, and their composition
techniques are limited to nested maps and arrays. In particular, they do not
natively support app-specific data models or APIs, although Yjs’s author has
noted the benefits of such an approach (Jahns, 2021). We compare collabs’s
performance to these libraries in Section 7.

Other libraries that provide RDTs for web apps include ShareDB (Smith and
Gentle, 2022), Legion (van der Linde et al., 2017), Fluid Framework (Fluid
Framework, 2022), and OWebSync (Jannes et al., 2021). Note that unlike Yjs,
Automerge, and collabs’s CRDTs, these depend on a central server. ShareDB and
Fluid Framework are notable for allowing programmer-added implementations, but
they do not support composition. At a more philosophical level, Kleppmann et
al. (2018b, 2019); van Hardenberg and Kleppmann (2020) describe how web CRDT
libraries can be used to make decentralized, end-to-end encrypted, and local-
first collaborative apps, while MobX’s documentation advocates for using
class-based, app-specific RDTs even in traditional client-server web apps
(MobX, 2022).

Several works describe or implement composition techniques for op-based CRDTs.
The collabs library is heavily influenced by these works, and our CRDT
implementations use compositional designs whenever possible. Leijnse et al.
(2019) describe classic op-based CRDTs in terms of compositional designs.
Kleppmann and Beresford (2017) design a CRDT for JSON-formatted data that is
motivated in terms of nested maps and arrays. Wallace (2019) describe Figma’s
real-time collaboration strategy, which uses a JSON-like tree of last-writer-
wins registers. Weidner et al. (2020) design a somewhat complex compositional
construction for op-based CRDTs that they call the semidirect product.
Relative to the libraries mentioned here, collabs implements more composition
techniques and also allows arbitrary programmer-added ones; relative to the
theoretical papers, we give actual implementations for many of their
techniques.

Other works describe composition techniques for state-based CRDTs
(equivalently, lattices) (Shapiro et al., 2011a). State-based CRDTs are
orthogonal to collabs because they use a different replication model (gossip
instead of messaging), but we were still inspired by their techniques. Riak
(Basho, 2015), Bloom$\mbox{}^{L}$ (Conway et al., 2012), LVars (Kuper and
Newton, 2013), and Baquero et al. (2015) describe CRDT-valued maps and
“stores” that use several CRDTs side-by-side; these are the basis for our
LazyMutCMap and CObject (Section 4.1).

Invariant analysis techniques such as Hamsaz (Houshmand and Lesani, 2019)
provide an alternative to composition for designing app-specific RDTs. They
synthesize a replicated version of an app from its sequential code plus
programmer-specified invariants.

Our implementations use many specific algorithms or composition techniques
from prior works, which we cite in-line. In particular, Table 2 gives sources
for our CRDT implementations.

##  3\. The Collab Abstraction

In this section, we introduce an abstraction for modular and composable RDTs
that we call a _Collab_ , short for _collaborative data structure_.333We use
_collaborative_ to differentiate these from general RDTs while indicating a
prominent use case (collaborative apps), and _data structure_ to emphasize
that implementations with the same API shape can have different behaviors. We
also describe a TypeScript API realizing this abstraction and techniques for
working with it. These form the core of our work.

At a high level, a Collab is a data structure that is:

Collaborative (replicated):

The data structure is replicated on multiple devices, with the replicas
following some consistency model (e.g., strong eventual consistency).

Message-based:

Replicas of a Collab stay in sync by sending messages to each other, which
they assume are sent with some network guarantees (e.g., causal broadcast).

Modular:

Each Collab controls its own implementation and API. Concretely, each Collab
is a mutable class with typed mutator and accessor methods, plus _events_ that
describe changes as they happen (since changes may be asynchronous).
Initialization rules ensure that different replicas of the same Collab have
identical types.

Composable:

Collabs can be composed like ordinary (non-collaborative) data structures,
e.g., by forming objects or collections.

We describe precisely what Collabs are and how they work in Sections 3.1–3.6.

There are two sides to the Collab abstraction. On the outside, _app
programmers_ use Collabs in their apps, e.g., to support real-time
collaboration. To them, Collabs “look like” ordinary, local data structures,
like those found in the Java Collections framework. But under the hood,
changes to the Collab are replicated on all collaborating devices.

###### Example 3.1.

CCounter is a simple Collab that implements the _op-based counter CRDT_
(Shapiro et al., 2011a). Figures 4 and 4 show how it looks to an app
programmer: its API and usage are like an ordinary, non-replicated counter
object, except for the addition of Inc events that are emitted when the value
changes, possibly due to a remote operation. Internally, CCounter.inc() sends
an "inc" message to all replicas, which then increment their value and emit an
Inc event.

⬇

1class CCounter {

2 inc(): void;

3 get value(): number;

4 on(eventName: "Inc",

5 handler: /*...*/

6 );

7}

Figure 3. API of CCounter, a Collab implementing the op-based counter CRDT.

⬇

1// counter is a CCounter.

2// Increment its replicated value

3// when incrementButton is clicked:

4incrementButton.onclick = () => {

5 counter.inc();

6}

7// Update the display whenever we

8// receive an Inc event:

9counter.on("Inc", () => {

10 display.innerHTML =

11 counter.value.toString();

12});

Figure 4. Using a CCounter to control a collaborative counter in a web page.

On the inside of the Collab abstraction, _custom Collab programmers_ implement
Collabs, e.g., CRDT algorithms. They see the APIs described in Sections
3.2–3.4. Although app programmers are free to implement custom Collabs, they
usually only need to do so using _composition techniques_ (Section 3.5) that
hide the details of the Collab abstraction. Thus it is not necessary for app
programmers to understand this section before using the library.

###  3.1. Concepts and Motivation

We start by describing the Collab abstraction at a theoretical level,
independent of our concrete API and implementations.

Conceptually, a Collab is an RDT that:

  * •

is treated as a black box that sends and receives messages (Figure 7), and

  * •

is part of a tree of other Collabs, called the _Collab hierarchy_ (Figure 7).

Note that the root of the Collab hierarchy is a separate concept that we call
a Runtime. It is responsible for managing the entire tree and connecting to
other devices over the network.

Figure 5. A Collab.

Figure 6. The Collab hierarchy.

Figure 7. Message flow from a Collab to its replicas.

The Collab hierarchy is replicated on all collaborating devices in an app.
That is, each device creates the same tree structure, and Collabs at the same
tree locations on different devices are replicas of each other (in particular,
they have the same implementations). The Collab hierarchy can mutate during
the lifetime of an app, but it is kept consistent across devices.

To maintain this replication, Collabs send messages to their replicas on other
devices. These messages typically travel as shown in Figure 7: up the tree,
over to collaborating devices, and back down the tree. More generally, this
behavior is not mandatory; parent Collabs (internal nodes in the tree) are
still treated as black boxes by their own parents, and so they are free to
send and receive messages and manage their children however they like. For
example, a parent can choose to causally order messages before delivering them
to its children (see Section 3.6).

The black-box model plus the Collab hierarchy are what enable our work’s
unique combination of modularity and composability for RDTs. Modularity
follows from the black-box model: each Collab implementation is free to choose
its API shape, internal state, and algorithm independent of the rest of the
library, so long as it sends and receives messages. Composability follows from
the Collab hierarchy: composed Collabs have their components as children and
are free to manage those components however they like, enabling arbitrary
composition techniques.

##### Motivation

It remains to justify why these ideas are needed in the first place. Indeed,
no such abstraction is needed to enable modular and composable _local_ data
structures. However, in the replicated setting, there are two key challenges.

The first challenge is _identification across devices_ : when one Collab sends
a message, the sent message must be delivered to the replicas of that
particular Collab on other devices, not other Collabs in the same app. In
particular, if a Collab has several component Collabs, and devices instantiate
two independent copies of the composed Collab, then messages sent by the first
copy’s components must be delivered to replicas of the first copy’s
components, not the second copy’s. Since we permit arbitrary Collab
implementations, we cannot use simple schemes like a fixed set of available
instances per type, as used by Yjs (Jahns, 2022; Nicolaescu et al., 2016) and
Legion (van der Linde et al., 2017). Also, composed Collabs complicated UID-
based schemes like Fluid Framework’s (Fluid Framework, 2022). Instead, we use
the Collab hierarchy and its identification scheme: a Collab is identified by
its location in the tree.

The second challenge is _initialization across devices_ : when a Collab is
created on one device, replicas of it must be created on all other devices,
with the same tree location and implementation. Since implementations can be
arbitrary and possibly infinite in number (e.g., parametrized by constructor
arguments or generic types), we cannot use existing techniques, which rely on
a fixed set of available RDT instances (Yjs (Jahns, 2022; Nicolaescu et al.,
2016), Legion (van der Linde et al., 2017)) or instance creation messages that
specify the type in an enum (Yjs (Jahns, 2022; Nicolaescu et al., 2016),
Automerge (contributors, 2022), Fluid Framework (Fluid Framework, 2022)).
Instead, the Collab abstraction lets parent Collabs instantiate children
however they like, and we describe several techniques that they can use in
Section 3.4.2.

###  3.2. Collab API

Concretely, the collabs library implements the Collab abstraction as an
abstract class. It is the base class for all collaborative data structures
using the library.

Figure 8 shows Collab’s API. We now describe this API in detail.

⬇

1abstract class Collab<Events> {

2 // Messaging

3 protected send(messagePath: Message[]): void;

4 abstract receive(messagePath: Message[], meta: MessageMeta): void;

5

6 // Saving and Loading

7 abstract save(): Uint8Array;

8 abstract load(saveData: Optional<Uint8Array>): void;

9

10 // Events

11 on<K>(eventName: K, handler: (event: Events[K], caller: this) => void):
Unsubscribe;

12 protected emit<K extends keyof Events>(eventName: K, event: Events[K]):
void;

13

14 // Collab Hierarchy

15 readonly parent: CollabParent;

16 readonly name: string;

17 readonly runtime: Runtime;

18 constructor(initToken: InitToken);

19}

Figure 8. The Collab abstract class (slightly simplified).

##### Messaging

The send method lets the Collab send serialized messages. Sent messages are
delivered to receive on all replicas of the Collab.

Each Collab must (informally) specify its _network assumptions_ , i.e., its
assumptions about when and whether messages are delivered to receive, and its
_consistency guarantees_ in the sense of Viotti and Vukolić (2016), i.e.,
under what conditions replicas will have identical externally-visible states.
Programmers using the Collab are expected to satisfy its network assumptions
by embedding it within the proper environment (see Section 3.4.1 below).

The contract of receive is then: _Given the stated network assumptions,
receive updates the internal state so that the stated consistency guarantees
hold._

###### Example 3.2.

Our op-based CRDTs (Section 5) assume _causal broadcast_ (Birman and Joseph,
1987): sent messages are delivered immediately to the sender’s receive method,
and exactly once in causal order (Lamport, 1978) to all other replica’s
receive methods. In return, they guarantee _strong eventual consistency_
(Shapiro et al., 2011b): any two replicas that have receive’d the same
messages will have identical externally-visible states.

Note that replicas can send arrays of messages (messagePath); this is a
convenience for the Collab hierarchy, discussed below. The _meta_ parameter in
receive gives basic metadata about the message, e.g., its sending device; it
can be extended to include arbitrary additional metadata.

##### Saving and Loading

The save method must serialize the Collab’s internal state into a byte array
(Uint8Array) that can later be loaded on a new replica using load. The
contract is: _Loading save data is equivalent to receiving all messages that
the saver received before saving._ This is important in practice for getting
new replicas up to speed—e.g., a new collaborator on a shared document, or a
refreshed browser tab.

Programmers using the Collab must ensure that _load_ is called exactly once,
after the Collab is initialized but before it is used—again by embedding it
within the proper environment (Section 3.4.2). Note that _saveData_ is
optional because a Collab might have no prior save data.

##### Events

From the programmer’s perspective, a key difference between a Collab and a
local data structure is that a Collab can change asynchronously, due to
received network messages.444Note that because JavaScript is single-threaded,
such changes cannot interrupt other running code. _Events_ notify the
programmer when this happens so that they can update their own views of the
Collab (e.g., the GUI). The programmer registers handlers using on, while the
Collab emits events using emit. The Events generic type allows Collab
implementations to specify events’ names and types.

The preferred contract for events is: _Events describe how to replay the
Collab’s changes on a local data structure._ A weaker, but still useful,
contract is: _Whenever the Collab’s externally-visible state changes, it emits
the built-in “Any” event._

##### Collab Hierarchy

To construct the Collab hierarchy described in Section 3.1, each Collab is
assigned a _parent_ and _name_ in its constructor, via the initToken
constructor argument. The parent has type CollabParent, which can be either
another Collab or an instance of the interface Runtime, which serves as the
root; these types are described in the next section (Section 3.3). The name
uniquely identifies the Collab among its siblings. Thus each Collab is
uniquely identified within its Runtime (stored in runtime) by the sequence of
names on its path to the root.

Collabs on different devices are considered replicas of each other if and only
if they have the same sequence of names on their paths to the root.
Inductively, this is equivalent to the condition that their parents are
replicas of each other and they have the same names.

As we explain in Section 3.4 below, a Collab’s parent is ultimately
responsible for calling or handling the Collab’s send, receive, save, and load
methods. In particular, it inductively ensures that a message sent by one of
its children is delivered to the same-name child on other devices.

###  3.3. Auxiliary APIs: CollabParent and Runtime

In addition to the Collab abstract class, we define types CollabParent and
Runtime, shown in Figure 9. These describe parent (non-leaf) and root nodes in
the Collab hierarchy.

⬇

1interface ICollabParent {

2 childSend(child: Collab, messagePath: Message[]): void;

3}

4

5interface Runtime extends ICollabParent {

6 readonly replicaID: string;

7}

8

9type CollabParent = ICollabParent & (Collab | Runtime);

Figure 9. Auxiliary APIs used by the Collab hierarchy: CollabParent, its
helper ICollabParent, and Runtime. Some utility methods and events are
omitted.

CollabParent describes an object that can be a Collab’s parent: either another
Collab that implements the interface ICollabParent, or a Runtime. The
childSend method is called by its children’s Collab.send methods, as described
in Section 3.4 below.

A Runtime serves as the root of the Collab hierarchy. Since every Collab must
have a parent, it is not itself a Collab. The Runtime is ultimately
responsible for managing the Collab hierarchy, including initializing it,
delivering messages between devices, and loading and saving. How it does so is
app-specific and can vary widely, so Runtime is a minimal interface that
leaves out app programmer-facing methods; specific implementations must add
such methods for their use case. For example, CRDTRuntime (Section 5.1)
provides endpoints for sending and receiving messages and for loading and
saving the whole Collab hierarchy. Besides the CollabParent methods, Runtime
provides utilities for use by Collabs, such as a device-specific replicaID.

###  3.4. Runtime Behavior

We now describe the library’s behavior at runtime:555Not to be confused with
the Runtime interface, which provides part of this behavior. how messages are
delivered between Collab replicas and how Collabs’ lifecycles are managed.

###### Remark 3.3.

The behavior described in this section is mostly only relevant to programmers
writing custom Collab _parents_ , which are rare; for example, the table of
CRDT implementations in Section 5.3 (Table 2) contains only one. Thus in the
common case, programmers—even custom Collab programmers—do not need to learn
this behavior before using the library.

####  3.4.1. Message Delivery

When one replica of a Collab calls send, the sent message needs to be
delivered to all of its replica’s receive methods. We accomplish this using
the Collab hierarchy, as shown in Figure 7:

  1. (1)

The sent message passes up the Collab hierarchy from its sender to the root
Runtime.

  2. (2)

The Runtime delivers this message to the Runtimes on other devices in an app-
specific way. For example, CRDTRuntime (Section 5.1) defers to the app
programmer, by directly exposing a Send event and a receive method.

  3. (3)

Each recipient device’s Runtime passes the message back down the Collab
hierarchy to its own replica of the sending Collab.

Each recipient Collab’s receive method then updates its own internal state,
thus replicating the original operation.

In more detail, the implementation of Collab.send is:

⬇

protected send(messagePath: Message[]): void {

this.parent.childSend(this, messagePath);

}

Collab parents must then implement childSend in order to satisfy the contract:
_Assuming the parent’s network assumptions are satisfied, the parent in turn
satisfies its children’s network assumptions._ Figure 10 shows a typical
implementation. The parent tags the message with some metadata identifying the
child (e.g, its name), then calls its own Collab.send method to send it
further up the tree. The parent’s replicas on all devices receive the sent
message, strip the child-identifying metadata, and then deliver the message to
its own child. Other implementations are described in Section 3.6 below.

⬇

1childSend(child: Collab, messagePath: Message[]) {

2 messagePath.push(child.name); // Append name to identify child.

3 this.send(messagePath); // Send via own parent.

4}

5

6receive(messagePath: Message[], meta: MessageMeta) {

7 const childName = messagePath.pop();

8 const child = /* get child with name childName */;

9 child.receive(messagePath, meta);

10}

Figure 10. Sketch of childSend and receive in a typical parent Collab.

####  3.4.2. Collab Lifecycle

Each Collab goes through a lifecycle with the following stages:

Initialization:

The Collab is constructed and attached to the Collab hierarchy.

Loading:

Collab.load is called.

Use:

The Collab sends and receives messages. Its save method may also be called at
any time.

Disposal:

If the Collab is no longer needed, it may be detached from the Collab
hierarchy and allowed to be garbage collected.

As with message delivery, a Collab’s lifecycle is managed completely by its
parent. At the root, the Runtime manages its children, hence the entire Collab
hierarchy, in an app-specific way.

In particular, a Collab’s parent is responsible for initializing the Collab,
calling load and save (usually as part of the parent’s own load and save
methods), and disposing the Collab if desired. The contract for initialization
and disposal is: _Replicas of a CollabParent on different devices must have
the same children, with the same names and implementations (classes and
constructor arguments), modulo the parent’s stated consistency guarantees._

The trickiest part of the lifecycle is initialization. This is because we
require Collab replicas with the same name and parent to have the same
implementation on all devices, but these implementations can be arbitrary,
since we allow programmer-added Collabs instead of just our built-in ones.
While parents are free to handle initialization however they like (respecting
the above contract), we have found the following techniques useful in our own
CollabParent implementations:

Statically create children with common code:

In the parent’s constructor or synchronously afterwards666JavaScript is
single-threaded, so constructing children synchronously—in the same series of
instructions as the parent’s constructor call—prevents surprises in which the
parent receives a message before it is done initializing its children.,
initialize all of the parent’s children, using code that executes identically
on all devices. Typically, one ensures that code “executes identically” by
using the same codebase on all devices.777For web apps, this is a reasonable
assumption because the app can serve identical code to all clients and force
simultaneous version updates. However, using collabs is trickier if devices
might simultaneously run different code versions. We remark that the same is
true of other CRDT libraries, although Cambria (Litt et al., 2020) provides a
possible solution. See Figure 11 in Section 4.1 for an example.

Dynamically create children with a valueConstructor:

For collection types that dynamically create child Collabs (e.g., in response
to a click on a “New Document” GUI button), have the collection type take a
valueConstructor parameter in its own constructor. The valueConstructor inputs
arbitrary serializable arguments (e.g., an initial value for a new document),
plus a parent and name, then outputs a new Collab with the given parent and
name. To create a new Collab, the creating replica of the collection sends
appropriate arguments and a unique new name in a message to its other
replicas. Recievers then call valueConstructor with those arguments and name
and with themselves as the parent. So long as the valueConstructors behave
identically on all devices—i.e., they run the same code and are pure functions
of their inputs—this creates identical children on all devices.

###### Remark 3.4.

These techniques allow not just arbitrary Collab _implementations_ (i.e.,
classes), but also arbitrary _constructor arguments_ and _generic types_ , for
both fixed and dynamically-created Collabs. Constructor arguments let the
programmer customize Collabs; in particular, they allow specifying an initial
value, e.g., a text document pre-filled with sample text. This is in contrast
to existing libraries, which only support initial values for dynamically-
created CRDTs, occasionally confusing app programmers.888E.g., see
https://discuss.yjs.dev/t/initial-offline-value-of-a-shared-document/465 and
https://github.com/automerge/automerge/issues/273.

###  3.5. Composition

The Collab hierarchy allows _Collab composition_ : creating more complex
Collabs by combining simpler ones. Typically, the composed Collab is the
parent (or ancestor) of its components.

To make this concrete, recall the compositional rich-text CRDT from the
introduction (Figure 2). In terms of the Collab hierarchy:

  * •

Each CRichChar instance is the parent of its attributes map.

  * •

CRichText’s text field is the parent of all of its CRichChar values.

  * •

Each CRichText instance is the parent of its text field.

Because each Collab is a class, a composed Collab can encapsulate its
children, only exposing mutators and accessors as it sees fit. For example,
CRichText can choose to make its text field private, instead exposing the API
shown in the introduction (Figure 2). Also, due to the Collab hierarchy, a
composed Collab’s components (i.e., children) live in its own namespace. This
allows one to instantiate many instances of the composed Collab without name
conflicts between different instances’ components.

Typically, one designs composition techniques so that they preserve
correctness properties, especially consistency guarantees. For example, our
collections of CRDTs guarantee that if their values have strong eventual
consistency, then the collection as a whole has strong eventual
consistency—i.e., CRDT correctness composes. In general, each composition
technique should state its usage rules and the resulting guarantees.
Programmers using the technique then only need to verify compliance with those
rules, instead of proving consistency from scratch.

###  3.6. Generality

Our library supports a wide variety of behavior. An individual Collab can
already implement an arbitrary message-based RDT. The Collab hierarchy, and
the runtime behavior described in Section 3.4, permit even more general
behavior.

First, Collab subclasses can implement features that might otherwise need to
be built into the core runtime behavior. Some examples:

Causal ordering:

A parent can delay and deduplicate messages before delivering them to its
children, converting at-least-once reliable broadcast into exactly-once causal
order broadcast (CRDTMetaLayer, Section 5.1).

Message batching:

A parent can batch messages sent by its children, sending them as a single
message that all other devices process atomically.

Sandboxing:

A Collab can send and receive messages on behalf of a separate collabs app
running in an HTML IFrame (Containers, Section 6.1.2). This lets one connect
the IFrame’d app to an arbitrary network while sandboxing it from the outer
app.

Advanced composition techniques:

We already briefly described how a parent can dynamically create Collabs
(Section 3.4.2). One can also implement more complicated composition
techniques, such as the semidirect product of CRDTs (Weidner et al., 2020),
which modifies other Collabs’ operations (Section 5.2).

By allowing these features to be implemented as individual Collabs instead of
as core library features, we make them optional and also permit programmers to
add their own.

Second, the Runtime interface has many possible implementations. Our built-in
CRDTRuntime is network- and storage-agnostic (deferring these to the app
programmer), but other Runtimes could integrate directly with specific
backends. For example, Section 6.3 describes a web app that updates server-
side state by connecting its Collabs to server-side replicas over a WebSocket.

##  4\. Core Library

The collabs library is published as several npm
packages,999https://www.npmjs.com/org/collabs all written in TypeScript. The
bulk of the library comes in the packages
@collabs/core101010https://www.npmjs.com/package/@collabs/core and
@collabs/crdts.111111https://www.npmjs.com/package/@collabs/crdts This section
discusses @collabs/core, while Section 5 describes @collabs/crdts.

The @collabs/core package includes APIs and implementations that are relevant
to the Collab abstraction in general. It includes the Collab abstract class
and related APIs described in the previous section. Additionally, it includes
features that make the Collab abstraction easier to use, especially for
programmers implementing their own Collabs. The rest of this section
highlights some of those features.

###  4.1. Collab Implementations

The core library includes several Collab implementations that are not tied to
a particular kind of RDT. This includes superclasses that make it easier to
implement custom Collabs than by subclassing Collab directly. We now highlight
some of these implementations.

CPrimitive is an abstract subclass of Collab that one can extend to implement
a “primitive Collab”: a Collab with no children, i.e., a leaf in the Collab
hierarchy. CPrimitive lets subclasses directly send and receive messages, so
it is appropriate for implementing any traditional (non-composed) RDT
algorithm written in that style.

CObject is a concrete subclass of Collab that one can further subclass to make
a _Collab object_ : an object whose instance fields are themselves Collabs.
Collab objects can apply standard object-oriented programming techniques,
e.g., encapsulation or further subclassing.

Figure 11 shows an example CObject subclass. Note that although this is a
custom Collab, it is simple enough that we expect app programmers to use
Collab subclasses like this to model their own data, not just custom Collab
programmers. In particular, its code is similar to composing normal, non-
collaborative data structures; the implementer does not need to consider
message-passing or consistency guarantees.

⬇

1class CPoll {

2 private readonly yesVotes: CCounter;

3 private readonly noVotes: CCounter;

4

5 constructor(initToken: InitToken) {

6 super(initToken);

7

8 this.yesVotes = super.addChild("yesVotes", Pre(CCounter)(0));

9 this.noVotes = super.addChild("noVotes", Pre(CCounter)(0));

10 }

11

12 voteYes(): void {

13 this.yesVotes.inc();

14 }

15

16 voteNo(): void {

17 this.noVotes.inc();

18 }

19

20 hasMajority(): boolean {

21 return this.yesVotes.value > this.noVotes.value;

22 }

23}

Figure 11. Implementation of a collaborative poll CRDT, CPoll, as a CObject
subclass. The addChild calls in the constructor create children with the given
child names, classes, and constructor arguments (here an initial value of 0).
Pre is a higher-order function that curries CCounter’s initToken constructor
argument so that it can be provided inside addChild.

In terms of the Collab hierarchy, a CObject subclass’s instance fields are its
children. These are finite in number and each have a unique name—e.g., the
instance field’s programmatic name, or for better performance, a minimum-
length unique name. Names are assigned during the addChild calls in the
subclass constructor. The CObject base class manages its children using the
“typical parent” behavior described in Section 3.4: it multiplexes its
children’s sent messages and save data, keyed by name, without further
processing.

LazyMutCMap<K, C> is similar to CObject, but with children of type $C$ indexed
by _keys_ of an arbitrary serializable type $K$, instead of by a fixed finite
set of names. Since the key space may be infinite, children are constructed
lazily on each replica: either when requested by the local user via get(key),
or when a message for that child is received from another replica. To avoid
memory leaks, children are forgotten if they return to their initial state,
allowing them to be reclaimed by the JavaScript garbage
collector.121212JavaScript WeakRefs are used to ensure that a child is not
forgotten if the programmer holds a reference to it elsewhere.

###  4.2. Data Types

One of collabs’s goals is to be a “collections library” for collaborative data
structures. To this end, we include interfaces for collection types and other
common data types. Table 1 lists these interfaces.

Table 1. Interfaces for Collab data types. Interface | Ordinary Data Type |  Notes
---|---|---
CSet<T, AddArgs = [T]> | Set<T> |  See Section 4.2 for a description of AddArgs.
CList<T, InsertArgs = [T]> | Array<T> |  Mutators are insert and delete, which shift later elements—think linked list. InsertArgs are like CSet’s AddArgs.
CMap<K, V, SetArgs = [V]> | Map<K, V> |  SetArgs are like CSet’s AddArgs.
CVariable<T, SetArgs = [T]> |  Variable of type $T$ |  SetArgs are like CSet’s AddArgs.
CBoolean | boolean |

As an example, the CSet interface is similar to the API of TypeScript’s built-
in Set<T> class, but with two collaboration-related changes:

AddArgs:

Instead of inputting a value directly, add may accept arbitrary arguments
AddArgs. Generally, an implementation serializes those arguments and sends
them to other replicas; all replicas then use the arguments to construct the
actual value and add it to their internal state. By inputting AddArgs instead
of just literal values of type $T$ (the default), the CSet interface can
support not just serializable values but also values that must be constructed
separately on each device, e.g., dynamically-created Collab children or DOM
elements.

Events:

The interface specifies Add and Delete events, to be emitted when a value’s
presence in the set changes locally.

These data types reflect our own experience designing Collab collections and
provide advice to custom Collab programmers. They also ensure API consistency
for programmers using collections. We caution, however, that unlike typical
collection interfaces, they do not ensure _semantic_ consistency: different
implementations may behave very differently in the face of concurrent
operations, e.g., concurrently adding and deleting a value in a CSet.

##  5\. CRDT Library

We now discuss collabs’s CRDT library, @collabs/crdts. It includes a Runtime
implementation for CRDTs, helper classes for implementing CRDTs, and numerous
CRDT implementations. As with collabs in general, programmers are free to
extend the library with their own CRDTs.

###  5.1. CRDTRuntime and CRDTApp

CRDTRuntime is an implementation of the Runtime interface that provides an
environment for CRDTs. This environment has several features:

Causal broadcast:

CRDTRuntime guarantees causal broadcast to its descendant Collabs: messages
sent by one replica are delivered exactly once in causal order to all other
replica’s receive functions. This is the standard network assumptions for op-
based CRDTs (Shapiro et al., 2011a). It also guarantees _causal consistency_ ,
a desirable property for user-facing apps (Lloyd et al., 2011).

CRDT Metadata:

Many CRDT algorithms make use of vector clocks (Fidge, 1988; Mattern, 1989),
wall-clock times, or Lamport timestamps (Lamport, 1978). CRDTRuntime provides
this metadata by request as part of the MessageMeta delivered to Collabs’
receive methods, analogous to the tag in tagged reliable causal broadcast
(Baquero et al., 2014). This is easier and more efficient than forcing each
CRDT to send and store such metadata itself.

Batching and transactions:

Messages sent close together are batched into a single network message that
all other devices process atomically, i.e., in a synchronous sequence without
interruption by other messages. This implements a weak form of transactions,
and also reduces network usage by deduplicating repeated portions of messages
in a batch.

To let app programmers use CRDTs, we provide the class CRDTApp. It is a thin
wrapper around a CRDTRuntime that exposes only the features relevant to app
programmers. In particular, it has a registerCollab method that lets the app
programmer instantiate Collabs and attach them to the Collab hierarchy as
descendants of the CRDTRuntime; see Figure 12 for a usage example. These
Collabs serve as the top-level state and must instantiate all other Collabs as
their descendants. CRDTApp also provides endpoints for sending and receiving
messages and for loading and saving the whole Collab hierarchy.

⬇

1const app = new CRDTApp();

2const likesCats: CPoll = app.registerCollab("likesCats", Pre(CPoll)());

3const likesDogs: CPoll = app.registerCollab("likesDogs", Pre(CPoll)());

4// Connect app to a network and storage...

5// Use likesCats and likesDogs in a collaborative app...

Figure 12. Example usage of CRDTApp.registerCollab to set up a CRDT-based
app’s collaborative state. Here the state consists of two polls about animals,
ultimately instantiating four CCounters—two as the children of each CPoll. As
usual for Collab children (see Section 3.4.2), these Collabs must have
distinct names, and they must be registered identically on all collaborating
devices. Pre is as in Figure 11.

###  5.2. CRDT Implementation Helpers

We complement the Collab superclasses described in Section 4.1 with several
CRDT-specific implementation helpers.

PrimitiveCRDT is like CPrimitive (Section 4.1) except that it also
conveniently exposes the CRDT metadata provided by CRDTRuntime. That is, it is
an abstract class that one can extend to implement a “primitive CRDT”: an op-
based CRDT written in the traditional message-passing style that may also
consult vector clock entries, a wall-clock time, and a Lamport timestamp.

SemdirectProductStore implements the _semidirect product of CRDTs_ (Weidner et
al., 2020). This is a somewhat complex compositional construction that allows
one to combine the operations of two CRDTs, so long as one specifies an
_action_ function satisfying certain algebraic properties. To our knowledge,
it has not been previously implemented.

Weidner et al. describe the semidirect product in terms of message
modification: when a replica receives a message for the first component CRDT,
instead of delivering it as-is, the semidirect product first modifies it using
the action. While we provide one implementation in this style—a custom parent
Collab that is a parent to the component CRDTs and modifies child messages
before delivering them—it violates encapsulation, since it requires the action
function to understand how component CRDTs’ messages are encoded.

Instead, we provide SemidirectProductStore, a semidirect product store that
lets the programmer describe operations in a format of their choice. To
perform an operation, the programmer first broadcasts a description of the
desired operation, either by sending custom messages or by performing
operations on other Collabs. Upon receipt, they pass this description to
SemidirectProductStore, which applies the action function and outputs a
description of the actual operation to perform, again in a format chosen by
the programmer. The programmer must then perform the described operation
_locally_ —on the local replica only—because this is happening on every
replica, due to the original broadcast. We make such local operations possible
via RunLocallyLayer, a parent Collab that stops sent messages from being sent
further up the Collab hierarchy, so that they do not affect remote replicas.
The result is that we only interact with component Collabs through their
public-facing APIs (i.e., public methods).

###  5.3. CRDT Implementations

Table 2 lists a selection of our CRDT implementations. We follow it with some
general comments.

Table 2. Selected CRDT implementations from @collabs/crdts. $T$ can be any immutable and serializable type, while $C$ must be a Collab subtype. CRDT |  Ordinary Data Type |  Implementation Technique |  Notes
---|---|---|---
TrueWinsCBoolean |  boolean |  Primitive CRDT |  Enable-wins flag (Basho, 2015)
ResettableCCounter |  number |  Primitive CRDT |  Weidner and Almeida (2022), first known implementation
CNumber |  number |  Semidirect product |  Example 3.1 by Weidner et al. (2020), first known implementation
CText |  string |  Primitive CRDT |  Variant of Logoot list CRDT (Weiss et al., 2009)
LWWCVariable<T> |  Variable of type $T$ |  Primitive CRDT |  Causal last-writer-wins register (Leijnse et al., 2019)
LWWCMap<K, V> |  Map<K, V> |  CObject |
AddWinsCSet<T> |  Set<T> |  CObject |  Add-wins set (Shapiro et al., 2011b); implementation follows (Leijnse et al., 2019)
DeletingMutCSet<C> |  Set<C> |  Custom parent Collab |  Inspired by Yjs’s collections of CRDTs (Jahns, 2022; Nicolaescu et al., 2016)
ArchivingMutCSet<C> |  Set<C> |  CObject |  Alternate semantics to DeletingMutCSet (see main text)
DeletingMutCList<C> |  Array<C> |  CObject |  List-with-move by Kleppmann (2020b), first known implementation

##### Collections of Collabs

Some of our CRDTs, like DeletingMutCList, are collections of Collabs: their
values are themselves Collabs. Using Collabs for values is necessary when one
wants a collection’s values to be mutable, since then changes to a value on
one device are replicated to all devices. For example, a presentation editor
could represent each slide as a CRDT, then represent the whole presentation as
a DeletingMutCList of slide CRDTs.

Adding values to a collection of Collabs is tricky because the values must be
created dynamically by the collection itself, simultaneously on all devices
(modulo strong eventual consistency). We accomplish this using the
valueConstructor pattern described in Section 3.4.2. This allows our
collections of Collabs to have arbitrary Collab values, including programmer-
added Collabs, and also allows them to pass arbitrary arguments to their
values’ constructors.

Each collection of Collabs comes in two variations: Deleting and Archiving.
These differ in how they handle deleted values. In Deleting collections,
deleted values are disposed (detached from the Collab hierarchy) and can no
longer be used. In Archiving collections, deleted values are merely marked as
deleted using an AddWinsCSet; they can continue to be used and can be restored
later. Deleting is more memory-efficient: deleted values do not occupy memory
forever. Archiving is friendlier to collaborative app users: if one user
deletes a Collab that another user edits concurrently, then the second user’s
edits are not lost.

##### Implementation via Composition

Observe that many of the CRDTs in Table 2 are implemented via composition:
either as CObjects or as semidirect products. This made it easy to implement
them and to guarantee strong eventual consistency, relative to traditional op-
based CRDTs that send messages directly and require commutativity proofs.

The CObject subclasses are especially simple: instead of sending messages
directly, they wrap one or more other CRDTs, then perform all of their
operations by calling methods on descendants. For example, DeletingMutCList
has the compositional structure shown in Figure 13. This almost directly
implements Kleppmann (2020b)’s description of a list-with-move CRDT.

⬇

1class CEntry<C> extends CObject {

2 readonly value: C;

3 readonly position: LwwCVariable<ListPosition>;

4}

5

6class DeletingMutCList<C> extends CObject {

7 readonly set: CSet<CEntry<C>>

8 readonly positionSource: ListPositionSource<CEntry<C>>;

9 // ListPositionSource comes from CText’s implementation.

10}

Figure 13. Compositional structure of DeletingMutCList, a list of Collabs with
a _move_ operation. The set stores a set of entries (value, current position);
sorting these entries by position gives the user-visible list. Setting
entry.position to a new list CRDT position, obtained from positionSource,
moves that entry’s value without affecting concurrent operations on the value.

The primitive CRDTs and DeletingMutCSet do send their own messages, but of
these, only ResettableCCounter and CText use nontrivial CRDT algorithms. Thus
the library’s algorithmic foundation is mostly simple.

##  6\. Demos

We now turn to evaluation. This section describes demos made using the
library, while the Section 7 describes performance benchmarks. Our demos show
that collabs can be used to implement realistic collaborative apps,
interesting additional CRDTs, and traditional web apps.

###  6.1. Collaborative Apps

We implemented numerous collaborative web apps using collabs’s CRDTs. Because
they use CRDTs, these apps support collaboration over an arbitrary broadcast
network with arbitrary latency. In particular, they permit not just
traditional server-centric real-time collaboration but also end-to-end
encrypted collaboration, offline editing, LAN/subgroup collaboration,
decentralized networks, and local-first deployments (Kleppmann et al., 2019).

Each app is written in a style similar to the counter app in Figure 4: it
stores its collaborative state in collabs CRDTs; its GUI is a view of that
state, updated in response to CRDT events (either local or remote); and it
maps user inputs to CRDT method calls. For example, our (collaborative) plain
text editor stores its text in CText, while our whiteboard stores a map from
pixel coordinates to their color in an LwwCMap<[x: number, y: number],
string>.

The more complex apps model their state using custom CRDTs implemented with
collabs’s composition techniques. In particular, our rich-text editor uses the
compositional design from the introduction (Figure 2), including its
semidirect product of CRDTs.

We further demonstrated the semidirect product with a prototype in which users
can translate, rotate, and reflect shapes either individually or as a group,
like in a presentation editor. It enforces the intuitive but tricky-to-
implement behavior shown in Figure 14: if one user translates a shape, while
concurrently, another user rotates a whole group of shapes, then the
translation happens “within the rotated group”, i.e., its translation vector
is also affected by the rotation.

Figure 14. The result (right) of a concurrent translation (top) and group
rotation (bottom) in our shape demo.

####  6.1.1. Decentralized Networks

We demonstrated that collabs can be used over decentralized networks by
deploying it over the Matrix federated chat protocol131313https://matrix.org/.

To connect our demo apps to Matrix, we made them available as Matrix
widgets141414https://github.com/matrix-org/matrix-widget-api. This allows a
user to embed an app in an IFrame alongside a group chat; the app then sends
its Collab messages through the group chat. End-to-end encryption and access
control are managed by Matrix. To deploy the app, the app’s programmer only
needs to publish it as a static web page; this is much easier and cheaper than
deploying a traditional server-centric collaborative app. It thus
_democratizes_ collaborative app deployment, putting it within reach of
individuals and open-source projects, instead of just the businesses who run
most current collaborative apps.

Figure 15. Message flow for a Collab in a collabs container.

####  6.1.2. Containers

While our demo apps are network-agnostic, at some point, one must choose a
specific network—a server, Matrix, WebRTC, etc. It is inconvenient to rebuild
each app once for each network. Instead, we developed _collabs containers_:
network-agnostic, self-contained apps deployed using a static file. Users can
then pair a collabs container with any _container host_ , which connects the
container to a specific network.

Specifically, a collabs container is a collabs CRDT app that uses the class
CRDTContainer from package @collabs/container in place of CRDTApp, and that is
packaged as a single HTML file with all code and assets inlined.151515We
provide a template that is set up to build these self-contained HTML files.
CRDTContainer is like CRDTApp except that it leaves out the network and
storage endpoints, since it handles those internally.

A container host is another collabs CRDT app that uses the Collab
CRDTContainerHost from package @collabs/container. CRDTContainerHost behaves
like a primitive CRDT from the perspective of the Collab hierarchy, but
internally, it sends and receives messages on behalf of a collabs container
loaded into an IFrame, as shown in Figure 15. Thus the collabs container
ultimately uses the same network and storage as its host app. As usual, the
Collab abstraction’s generality (Section 3.6) meant that we could implement
CRDTContainerHost without explicit library support, despite the challenges
created by cross-IFrame communication’s asynchronous nature.

###  6.2. Additional CRDTs

We implemented additional CRDTs outside of the collabs library. These
demonstrate collabs’s utility as a library for implementing CRDTs, not just
using our provided ones.

##### JSON

Kleppmann and Beresford (2017) describe a CRDT for JSON-formatted data. We
implemented a similar CRDT inspired by their semantics. The implementation
uses composition techniques, namely, CObjects and collections of CRDTs, to
easily implement all of its conflict-resolution behavior. This demonstrates
that it is possible to model even complex data in collabs.

##### Tensor Averaging

Tensor averaging is a problem from numerical computing in which one takes a
coordinate-wise average of tensors (generalized matrices). We implemented a
novel CRDT that computes a running average of tensors, with operations to add
a new tensor and to reset the running average, by generalizing Weidner and
Almeida (2022). This could be used in federated learning (McMahan et al.,
2017) to aggregate gradient/weight updates from different nodes without the
need for a central instance.

###  6.3. Traditional Web App

Our final demo does not use CRDTs. Instead, it is a traditional web app that
synchronizes client-server state using collabs.

The app is a shared 3D room in which each user controls an avatar. Each user
can move their avatar, change their display name and color, and add furniture
to the room.

To manage the state, we compositionally define a custom Collab, RoomState,
that holds the app’s entire replicated state—all players’ names, positions,
etc., and all furniture in the room. Instead of CRDTs, it uses _sequentially
consistent_ replicated data types: the server echoes messages in a consistent
total order to all clients, which process these messages in order. The server
and each client instantiate a replica of RoomState within SerialRuntime, a
custom Runtime, and connect to each other over WebSockets.

With this setup, clients and the server can manipulate the shared state as if
it were a local data structure. For example, when a user changes their display
name, their client merely sets it:

⬇

ourPlayer.state.displayName.value = nameInput.value;

Likewise, adding new features to the state is hardly more complicated than
adding them to a class. For example, to allow users to choose their avatar’s
color, we added a hue field to the PlayerState class as a CObject child. This
was nearly as simple as adding a field to an ordinary class; in particular, we
did not need to consider networking (messages, HTTP endpoints, etc.) at all.
We expect that one could add further traditional web app features (e.g., input
validation and partial replication) by modifying SerialRuntime.

##  7\. Benchmarks

We now evaluate the performance of collabs’s built-in CRDT implementations.
This is not quite the same as evaluating collabs as a whole, since programmers
are free to implement their own Collabs, including non-CRDTs. However, it at
least shows what kind of performance is possible with the library. Also, we
expect that our CRDT implementations will be the most-used Collabs in
practice.

Section 7.1 benchmarks the performance of individual CRDTs on both synthetic
and recorded operation traces, in which we perform a fixed sequence of CRDT
operations. Section 7.2 investigates the end-to-end performance of a geo-
distributed app running in 100 browsers. In both sections, we compare collabs
to Yjs version 13.5.34 (Jahns, 2022; Nicolaescu et al., 2016) and Automerge
version 1.0.1-preview.7 (contributors, 2022); as described in Section 2, these
are the most similar existing CRDT libraries.161616The library versions were
current as of April 2022.

###  7.1. Individual CRDTs

We benchmarked each library’s CRDT versions of maps, variables, plain text,
and nested todo-lists using various editing traces. These benchmarks are based
on benchmarks for Yjs (Jahns, 2020b) and Automerge (Kleppmann, 2020a).

For maps and variables, the traces perform 10,000 random set operations. For
plain text, we use a trace by Kleppmann (2020a) (“RealText”) that replays the
character-by-character editing trace of a published paper (Kleppmann and
Beresford, 2017), totaling 259,778 operations. The nested todo-list
(“TodoList”) simulates the state of a collaborative todo-list app in which
each item in the todo-list has a text field and a “done” checkmark, and items
can be nested under other items arbitrarily; this benchmarks collections of
CRDTs. Its trace performs 10,000 operations, each of which randomly adds or
deletes an item, inserts or deletes bulk text, or toggles a “done” field.

All benchmarks were run on an Ubuntu 20.04.1 LTS desktop with a 4-core Intel
i7-4790 CPU @ 3.60GHz and 16 GB of RAM. The JavaScript environment was Node.js
v16.13.1, with flags \--expose-gc. For time and memory measurements, means
were derived from 10 runs, which followed 5 excluded warmup runs. Memory usage
was determined by forcing a garbage collection and then immediately measuring
the used heap size, using the @airbnb/node-memwatch
library171717https://github.com/airbnb/node-memwatch. All reported memory
values are subtracted from a baseline measurement taken at the beginning of
each trial. Network traffic measurements are the number of _broadcast_ bytes
sent to other replicas.

Figure 16. Performance of individual CRDTs on micro- and macro-benchmarks.

Figure 16 shows various performance metrics for a single device performing all
trace operations sequentially. Although this does not involve the concurrency
that CRDTs are designed for, it is probably the common case for collaborative
apps. Running Time shows the average number of operations that the single user
performs per second, Memory Consumption shows the increase in memory usage by
the end of the trace for a second device that received all messages, and
Network Traffic shows the average number of bytes sent per operation.

For each metric, we see that collabs performs on par with Yjs, while Automerge
is less efficient, apparently due to its particular replication model. Also,
Collab’s absolute performance is very practical: its time and network usage
permit far more operations per second than any human user can generate, and
memory consumption is always just a few MB.

##### Multiple Devices

In addition to sequential operations, we compared collabs to Yjs181818We
omitted Automerge because its lower operations-per-second makes these
benchmarks time-consuming. on the same traces but with multiple simulated
devices, in two modes:

Concurrent mode:

100 devices perform operations concurrently, i.e., each device performs one
operation, then all devices receive each others’ messages, etc. This simulates
collaborative editing with many users.

Rotation mode:

1,000 times during the trace, the (sequential) sender is replaced with a new
device, i.e., it saves its state and a new device loads that state. This
simulates device rotation due to page loads and refreshes in web-based
collaborative apps.

For each mode, instead of benchmarking the (many) message senders, we
benchmarked a separate device that received all of their messages. These modes
serve as “stress tests”, checking for performance degradations that Figure 16
may hide.

Figure 17. Text editing benchmark repeated for different operation modes
involving multiple users.

Figure 17 show the results for the text editing trace (RealText). Here
“CollabsCG” stands for “collabs—Causality Guaranteed”, an implementation in
which we turn off collabs’s causal ordering checks (Section 5.1); this is
permitted when using collabs over a network that is inherently causally
ordered, e.g., one based on a central server or gossip. Observe that CollabCG
has essentially the same performance as in Figure 16, i.e., it is unaffected
by the “stress”. However, for normal collabs (with causal ordering checks),
the Running Time and Network Traffic degrade in concurrent mode, though still
not beyond the range of practicality. This is a design choice: we choose to
enforce causal ordering for causal consistency (Section 5.1), but in the
presence of 100 concurrent operations, this necessarily requires $\Omega(100)$
size messages (Charron-Bost, 1991). Meanwhile, Yjs—which does not enforce
causal ordering—sees its ops/second degrade further than collabs in both
Concurrent and Rotate modes, and its memory consumption degrades in Concurrent
mode.

##### Discussion

As noted earlier, these benchmarks necessarily evaluate individual CRDTs,
which is somewhat different from evaluting collabs as a whole. However, they
at least show that collabs is not limiting performance, i.e., it is possible
to implement CRDTs on top of collabs on par with the current state-of-the-art.
The one exception is the cost of enforcing causal ordering, but as explained
above, this overhead is necessary given our choice of causal consistency.

###  7.2. End-to-End Performance of a Geo-Distributed App with 100 Users

We performed an end-to-end
benchmark191919https://github.com/composablesys/collabs-e2e-benchmark using
OWebSync’s eDesigners case study (Jannes et al., 2021; Jannes, 2022). This is
a realistic collaborative app, complete with a web GUI, in which users can
create and move objects. To test the scaling limits of collabs, Yjs, and
Automerge, we used 100 of the simulated users from OWebSync’s benchmarks, each
performing one operation per second.202020We chose 100 users because it is the
maximum number of simultaneous editors allowed by Google Docs.

For geo-distribution, the users’ browsers were deployed in AWS’s eu-north-1
availability zone, while they were connected via a simple messaging server in
AWS’s us-east-2; this created $\approx 125$ ms round-trip latency between
users. Each user was deployed in a Docker container as part of a Kubernetes
cluster running on 25 m5.large AWS instances, giving each user $0.5$ virtual
CPUs. In each of seven trials, after creating an initial number of objects (20
or 2,000), users moved one random shape each second for four minutes. In the
analysis, we sub-selected a one minute interval in which all users were
active.212121Not all users became active immediately, presumably due to
container startup times.

Table 3. Summary statistics for the end-to-end benchmark across 100 users. $10000^{*}$ denotes our ceiling on latency measurements (10 seconds), used for lost or excessively delayed operations. $\pm$ gives the standard deviation across all users in all trials. # Objects | Library | End-to-End Latency (ms) | CPU Usage | Network Usage
---|---|---|---|---
50% | 90% | 99%
20 | collabs | 123 | 126 | 135 |  $33\pm 4$ % |  $27\pm 1$ KB/sec
20 | Yjs | 3840 | $10000^{*}$ | $10000^{*}$ |  $77\pm 7$ % |  $86\pm 1$ KB/sec
20 | Automerge | $10000^{*}$ | $10000^{*}$ | $10000^{*}$ |  $100\pm 0$ % |  $1564\pm 267$ KB/sec
2000 | collabs | 123 | 127 | 133 |  $34\pm 6$ % |  $27\pm 1$ KB/sec
2000 | Yjs | 467 | 4013 | $10000^{*}$ |  $76\pm 20$ % |  $74\pm 24$ KB/sec
2000 | Automerge | $10000^{*}$ | $10000^{*}$ | $10000^{*}$ |  $99\pm 4$ % |  $660\pm 299$ KB/sec

Table 3 shows performance metrics aggregated across all trials and users. Here
End-to-End Latency measures the time between one users’ performing an
operation and other users’ applying it to their own GUI.222222We rely on
timestamps in local log files to measure latency; we expect that these
timestamps were reasonably synchronized between users because they were
deployed in the same Kubernetes cluster in the same AWS availability zone. CPU
and network usage are per-user, averaged across all users and trials. Note
that because the central server routes all messages, causally-ordered message
delivery is guaranteed; thus we disable collabs’s causality checks, like with
Section 7.1’s CollabsCG.

We see that with 20 objects, the contention between users’ moving the same few
objects causes Yjs’s end-to-end latency to increase beyond our measurement
threshold (10 seconds) by the 90th percentile, while Automerge’s latency is
above the threshold by the 50th percentile in both experiments. Meanwhile,
collabs’s 99th percentile latency is only 135 ms, barely above the round-trip
latency of $\approx 125$ ms. collabs also performs much better in the lower-
contention scenario with 2,000 objects, and its network usage is practical in
all cases. This shows collabs’s good end-to-end performance with large numbers
of collaborators.

##  8\. Conclusion

In this work, we introduced the Collab abstraction and the collabs library
built around this abstraction. The collabs library enables modular and
composable replicated data types, including CRDTs, and also includes built-in
composition techniques and op-based CRDT implementations. Programmers can
extend the library with arbitrary Collab implementations and composition
techniques, allowing it to adapt to future RDT research.

Our demos show that one can use the collabs library to build decentralized
collaborative apps that can be deployed from a static web page. Additionally,
our benchmarks show that its CRDT implementations are performant and can
support a geo-distributed app with 100 simultaneous users. In the future, we
plan to use these features to develop and deploy collaborative apps for real
users.

###### Acknowledgements.

We thank Umut Acar for reading a draft of this paper, Kristof Jannes for
providing code for OWebSync’s eDesigners case study, and Ignacio Musetti for
implementing our minesweeper demo’s frontend. Matthew Weidner was supported by
an NDSEG Fellowship sponsored by the US Office of Naval Research. Benito
Geordie was supported by an REU sponsored by the US National Science
Foundation.

## References

  * (1)
  * AntidoteDB (2019) AntidoteDB. 2019\.  Datatypes in Antidote.  https://antidotedb.gitbook.io/documentation/architecture/datatypes.
  * Baquero et al. (2015) Carlos Baquero, Paulo Sérgio Almeida, Alcino Cunha, and Carla Ferreira. 2015.  _Composition of State-based CRDTs_.  Technical Report. HASLab, INESC TEC.  http://haslab.uminho.pt/cbm/files/crdtcompositionreport.pdf
  * Baquero et al. (2014) Carlos Baquero, Paulo Sérgio Almeida, and Ali Shoker. 2014.  Making Operation-Based CRDTs Operation-Based. In _14th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems_ _(DAIS 2014)_. Springer LNCS volume 8460, 126–140.  https://doi.org/10.1007/978-3-662-43352-2_11 A shorter paper with the same title appears in PaPEC 2014.
  * Basho (2015) Basho. 2015.  Riak datatypes.  http://github.com/basho.
  * Birman and Joseph (1987) Kenneth P. Birman and Thomas A. Joseph. 1987.  Reliable Communication in the Presence of Failures.  _ACM Trans. Comput. Syst._ 5, 1 (jan 1987), 47–76.  https://doi.org/10.1145/7351.7478
  * Burckhardt et al. (2014) Sebastian Burckhardt, Alexey Gotsman, Hongseok Yang, and Marek Zawirski. 2014.  Replicated Data Types: Specification, Verification, Optimality. In _Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ (San Diego, California, USA) _(POPL ’14)_. Association for Computing Machinery, New York, NY, USA, 271–284.  https://doi.org/10.1145/2535838.2535848
  * Charron-Bost (1991) Bernadette Charron-Bost. 1991\.  Concerning the Size of Logical Clocks in Distributed Systems.  _Inf. Process. Lett._ 39, 1 (jul 1991), 11–16.  https://doi.org/10.1016/0020-0190(91)90055-M
  * contributors (2022) Automerge contributors. 2022\.  Automerge.  https://automerge.org/
  * Conway et al. (2012) Neil Conway, William R. Marczak, Peter Alvaro, Joseph M. Hellerstein, and David Maier. 2012\.  Logic and Lattices for Distributed Programming. In _Proceedings of the Third ACM Symposium on Cloud Computing_ (San Jose, California) _(SoCC ’12)_. Association for Computing Machinery, New York, NY, USA, Article 1, 14 pages.  https://doi.org/10.1145/2391229.2391230
  * Fidge (1988) Colin J. Fidge. 1988\.  Timestamps in message-passing systems that preserve the partial ordering.  _Proceedings of the 11th Australian Computer Science Conference_ 10, 1 (1988), 56–66.
  * Fluid Framework (2022) Fluid Framework. 2022\.  Total order broadcast and eventual consistency.  https://fluidframework.com/docs/concepts/tob/.
  * Houshmand and Lesani (2019) Farzin Houshmand and Mohsen Lesani. 2019.  Hamsaz: Replication Coordination Analysis and Synthesis.  _Proc. ACM Program. Lang._ 3, POPL, Article 74 (jan 2019), 32 pages.  https://doi.org/10.1145/3290387
  * Imine et al. (2003) Abdessamad Imine, Pascal Molli, Gérald Oster, and Michaël Rusinowitch. 2003.  Proving Correctness of Transformation Functions in Real-Time Groupware. In _ECSCW 2003_ , Kari Kuutti, Eija Helena Karsten, Geraldine Fitzpatrick, Paul Dourish, and Kjeld Schmidt (Eds.). Springer Netherlands, Dordrecht, 277–293.
  * Jahns (2020a) Kevin Jahns. 2020a.  Are CRDTs suitable for shared editing?  https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/.
  * Jahns (2020b) Kevin Jahns. 2020b.  CRDT benchmarks.  https://github.com/dmonad/crdt-benchmarks.
  * Jahns (2021) Kevin Jahns. 2021\.  How we made Jupyter Notebooks collaborative with Yjs.  https://blog.jupyter.org/how-we-made-jupyter-notebooks-collaborative-with-yjs-b8dff6a9d8af.
  * Jahns (2022) Kevin Jahns. 2022\.  Yjs.  https://docs.yjs.dev/
  * Jannes (2022) Kristof Jannes. 2022\.  (personal communication).
  * Jannes et al. (2021) Kristof Jannes, Bert Lagaisse, and Wouter Joosen. 2021\.  OWebSync: Seamless Synchronization of Distributed Web Clients.  _IEEE Transactions on Parallel and Distributed Systems_ 32, 9 (2021), 2338–2351.  https://doi.org/10.1109/TPDS.2021.3066276
  * Kleppmann (2020a) Martin Kleppmann. 2020a.  Benchmarking resources for Automerge.  https://github.com/automerge/automerge-perf.
  * Kleppmann (2020b) Martin Kleppmann. 2020b.  _Moving Elements in List CRDTs_.  Association for Computing Machinery, New York, NY, USA.  https://doi.org/10.1145/3380787.3393677
  * Kleppmann and Beresford (2017) M. Kleppmann and A. R. Beresford. 2017.  A Conflict-Free Replicated JSON Datatype.  _IEEE Transactions on Parallel and Distributed Systems_ 28, 10 (2017), 2733–2746.  https://doi.org/10.1109/TPDS.2017.2697382
  * Kleppmann et al. (2018a) Martin Kleppmann, Victor B. F. Gomes, Dominic P. Mulligan, and Alastair R. Beresford. 2018a.  OpSets: Sequential Specifications for Replicated Datatypes (Extended Version).  https://doi.org/10.48550/ARXIV.1805.04263
  * Kleppmann et al. (2018b) Martin Kleppmann, Stephan A. Kollmann, Diana A. Vasile, and Alastair R. Beresford. 2018b.  From Secure Messaging to Secure Collaboration. In _Security Protocols XXVI_ , Vashek Matyáš, Petr Švenda, Frank Stajano, Bruce Christianson, and Jonathan Anderson (Eds.). Springer International Publishing, Cham, 179–185.
  * Kleppmann et al. (2019) Martin Kleppmann, Adam Wiggins, Peter van Hardenberg, and Mark McGranaghan. 2019.  Local-First Software: You Own Your Data, in Spite of the Cloud. In _Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software_ (Athens, Greece) _(Onward! 2019)_. Association for Computing Machinery, New York, NY, USA, 154–178.  https://doi.org/10.1145/3359591.3359737
  * Kuper and Newton (2013) Lindsey Kuper and Ryan R. Newton. 2013.  LVars: Lattice-Based Data Structures for Deterministic Parallelism. In _Proceedings of the 2nd ACM SIGPLAN Workshop on Functional High-Performance Computing_ (Boston, Massachusetts, USA) _(FHPC ’13)_. Association for Computing Machinery, New York, NY, USA, 71–84.  https://doi.org/10.1145/2502323.2502326
  * Lamport (1978) Leslie Lamport. 1978\.  Time, Clocks, and the Ordering of Events in a Distributed System.  _Commun. ACM_ 21, 7 (jul 1978), 558–565.  https://doi.org/10.1145/359545.359563
  * Leijnse et al. (2019) Adriaan Leijnse, Paulo Sérgio Almeida, and Carlos Baquero. 2019.  Higher-Order Patterns in Replicated Data Types. In _6th Workshop on Principles and Practice of Consistency for Distributed Data_ _(PaPoC 2019)_. ACM, Article 5.  https://doi.org/10.1145/3301419.3323971
  * Litt et al. (2021) Geoffrey Litt, Slim Lim, Martin Kleppmann, and Peter van Hardenberg. 2021.  _Peritext: A CRDT for Rich-Text Collaboration_.  Technical Report. Ink & Switch.  https://www.inkandswitch.com/peritext/.
  * Litt et al. (2020) Geoffrey Litt, Peter van Hardenberg, and Orion Henry. 2020\.  _Project Cambria: Translate your data with lenses_.  Technical Report. Ink & Switch.  https://www.inkandswitch.com/cambria/.
  * Lloyd et al. (2011) Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2011.  Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS. In _Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles_ (Cascais, Portugal) _(SOSP ’11)_. Association for Computing Machinery, New York, NY, USA, 401–416.  https://doi.org/10.1145/2043556.2043593
  * Mattern (1989) Friedemann Mattern. 1989\.  Virtual Time and Global States of Distributed Systems. In _Parallel and Distributed Algorithms_. North-Holland, 215–226.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017\.  Communication-Efficient Learning of Deep Networks from Decentralized Data. In _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ _(Proceedings of Machine Learning Research, Vol. 54)_ , Aarti Singh and Jerry Zhu (Eds.). PMLR, 1273–1282.  https://proceedings.mlr.press/v54/mcmahan17a.html
  * MobX (2022) MobX. 2022.  Defining data stores.  https://mobx.js.org/defining-data-stores.html.
  * Nicolaescu et al. (2016) Petru Nicolaescu, Kevin Jahns, Michael Derntl, and Ralf Klamma. 2016.  Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types. In _Proceedings of the 19th International Conference on Supporting Group Work_ (Sanibel Island, Florida, USA) _(GROUP ’16)_. Association for Computing Machinery, New York, NY, USA, 39–49.  https://doi.org/10.1145/2957276.2957310
  * Preguiça et al. (2018) Nuno M. Preguiça, Carlos Baquero, and Marc Shapiro. 2018\.  Conflict-free Replicated Data Types (CRDTs).  _CoRR_ abs/1805.06358 (2018).  arXiv:1805.06358 http://arxiv.org/abs/1805.06358
  * Ressel et al. (1996) Matthias Ressel, Doris Nitsche-Ruhland, and Rul Gunzenhäuser. 1996\.  An Integrating, Transformation-Oriented Approach to Concurrency Control and Undo in Group Editors. In _Proceedings of the 1996 ACM Conference on Computer Supported Cooperative Work_ (Boston, Massachusetts, USA) _(CSCW ’96)_. Association for Computing Machinery, New York, NY, USA, 288–297.  https://doi.org/10.1145/240080.240305
  * Shapiro et al. (2011a) Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011a.  _A comprehensive study of Convergent and Commutative Replicated Data Types_.  Research Report RR-7506. Inria – Centre Paris-Rocquencourt ; INRIA. 50 pages.  https://hal.inria.fr/inria-00555588
  * Shapiro et al. (2011b) Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011b.  Conflict-Free Replicated Data Types. In _Stabilization, Safety, and Security of Distributed Systems_ , Xavier Défago, Franck Petit, and Vincent Villain (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 386–400.
  * Smith and Gentle (2022) Nate Smith and Joseph Gentle. 2022.  ShareDB.  https://share.github.io/sharedb/
  * van der Linde et al. (2017) Albert van der Linde, Pedro Fouto, João Leitão, Nuno Preguiça, Santiago Castiñeira, and Annette Bieniusa. 2017\.  Legion: Enriching Internet Services with Peer-to-Peer Interactions. In _Proceedings of the 26th International Conference on World Wide Web_ (Perth, Australia) _(WWW ’17)_. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, Switzerland, 283–292.  https://doi.org/10.1145/3038912.3052673
  * van der Linde et al. (2016) Albert van der Linde, João Leitão, and Nuno Preguiça. 2016.  $\Delta$-CRDTs: making $\delta$-CRDTs delta-based. In _Proceedings of the 2nd Workshop on the Principles and Practice of Consistency for Distributed Data_. ACM, 12\.
  * van Hardenberg and Kleppmann (2020) Peter van Hardenberg and Martin Kleppmann. 2020.  _PushPin: Towards Production-Quality Peer-to-Peer Collaboration_.  Association for Computing Machinery, New York, NY, USA.  https://doi.org/10.1145/3380787.3393683
  * Viotti and Vukolić (2016) Paolo Viotti and Marko Vukolić. 2016.  Consistency in Non-Transactional Distributed Storage Systems.  _ACM Comput. Surv._ 49, 1, Article 19 (jun 2016), 34 pages.  https://doi.org/10.1145/2926965
  * Wallace (2019) Evan Wallace. 2019\.  _How Figma’s multiplayer technology works_.  Technical Report. Figma.  https://www.figma.com/blog/how-figmas-multiplayer-technology-works/.
  * Weidner and Almeida (2022) Matthew Weidner and Paulo Sérgio Almeida. 2022.  An Oblivious Observed-Reset Embeddable Replicated Counter. In _Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data_ (Rennes, France) _(PaPoC ’22)_. Association for Computing Machinery, New York, NY, USA, 47–52.  https://doi.org/10.1145/3517209.3524084
  * Weidner et al. (2020) Matthew Weidner, Heather Miller, and Christopher Meiklejohn. 2020\.  Composing and decomposing op-based CRDTs with semidirect products.  _Proc. ACM Program. Lang._ 4, ICFP (Aug. 2020), 1–27.
  * Weiss et al. (2009) Stephane Weiss, Pascal Urso, and Pascal Molli. 2009\.  Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks. In _29th IEEE International Conference on Distributed Computing Systems_ _(ICDCS 2009)_. IEEE, 404–412.  https://doi.org/10.1109/ICDCS.2009.75