CRDT and OT generalize as
Time Machines

Version 2 (outline)

[ authors ]

Abstract: CRDT and OT are typically seen as competing approaches, but we show that they are instances of a more general concept: a Time Machine.

A Time Machine combines the abilities of both OT and CRDT and achieves things neither could do alone -- we can now create fully P2P systems that guarantee consistency, under arbitrary edits, over arbitrary network conditions, with improved performance, that can prune and forget old history, or share aspects of history in modules, with a common network protocol.

Introduction

If you read hacker news, you might see people contrasting OT and CRDT as approaches to collaborative editing:

You might see people arguing for advantages of one or the other:

This could lead you to think that and one might win over the other:

I was wrong: CRDTs are the future (an old OT developer, going CRDT)

But the model where programmers must choose between CRDT and OT is inaccurate:

                         Programmer Choice
                                 o
                                / \
                               /   \
                              V     V
                            CRDT    OT

A better model is:

                         System Capabilities

                         CRDT
                          ^
                          |
                          |
                          |
                          +-------------> OT

CRDT and OT are abilities that an algorithm can support. A Time Machine supports both:

                         System Capabilities

                         CRDT
                          ^             • <-- Time Machine
                          |
                          |
                          |
                          +-------------> OT

A Time Machine is a CRDT that can be used to do OT. It features the best of both worlds:

A CRDT's guaranteed consistency
OT's ability to refactor and prune historical metadata

This article explains the Time Machine, its benefits, and demonstrates:

a Time Machine enabling the world's first peer-to-peer collaborative text editor that prunes history
the world's fastest text CRDT
any CRDT client in 70 lines of code
a common network protocol for any CRDT or OT

OT and CRDT as Time Machine

The general problem is:

Multiple peers with snapshots to sync
They all edit at different times. There exists a partial order of edits— a Time DAG, representing a polythread of distributed execution.

Each peer traces a timeline through this DAG.

        o        o        o
        |        |        |
        A        A        B
        |        |/      \|
        C        B'       A'
        |/      \|       \|
        B''      C'       C'

At each merge o, the timeline incorporates operations from other branches
Challenge of OT & CRDT: to merge operations from remote peers, consistently, in any order
But those operations look different, in different branches of time.
- [example] of text address change
- [example] of text deletion does nothing if already deleted
- [example] of register value change overriding this one

Operational Transform asks the question of how to convert operations onto other lines of time.

OT is Rebase

Rebase moves an op to a new place in time. Goal: produce the same snapshot of state.

      o    OH
      |
      o
  .../.\
  . o . o             <-- should it be only one version at a time?
  . | . |
  . o . o
  ..... |
      .....
      .   .
      .   .
      .   .
      .....

To Merge: Move it to the local current version, which might have new changes
As it rebases, it has to update the address and effect of the change
- [example] of text address change
- [example] of text deletion does nothing if already deleted
- [example] of register value change overridding this one
This transforms a DAG of changes into each peer's distinct line of changes.
- The rebased edit can be applied natively to each peer's local timeline
$Travel : (op, from, to) \mapsto op'$
This idea is right! But implementing transform is hard.
- Simple to do the simple case: add one op, remove one op
  - $T (op1, op2) \mapsto op1'$
- Idea: apply this iteratively to all the ops!
  [ diagram? ]
- But doing it for N peers (TP2) became too challenging to solve
  - N papers claimed to succeed, but later were found out to be failures
  - Then proven impossible without adding information to the process
First solution: TTF -- added an internal format
- Creates what we call "Collapsed History" -- a format that collapses past edits down into the state
- A read() function can convert to the snapshot
- This worked!
- The authors realized the internal format was key, and published a paper that focused entirely on the internal format called WOOT...

CRDT merges through a Collapsed History

Whereas OT operates on Observable History (OH), CRDT converts all observed edits into an internal format, that we call Collapsed History (CH):

      o    OH
      |
      o
     / \
    o   o
    |   |
    o   o
      
   ---|---
      v
           CH
     (*)

These collapses are like "Data Laced with History", they get closer to an observable snapshot of the state than the list of raw operations, but they still contain history.

Then we can compute an observation of the current version. $View : CH \to Snap$

Example Collapses:

Space Dags (woot, sync9, fugue, rga)
Fractional indexing
Registers
Counters / Max [ collapse everything ]
Append-only logs [ collapse nothing ]

General rules: [ callout box ]

The data structures that merge are created by collapsing time
- Put things in space close together [space dag]
- Remove/obliterate content that is overridden [registers]
- Keep ambiguities in content where merging needs them [space dag branch]

Problems with CRDT

It gets consistency, but...
Everything depends on ever-growing history blob
- Edits depend on all prior edits, since $s^0$ . No pruning in general. Can grow huuuuge!
- Peers depend on collapse algorithm (can get complex!) to read or write edits

Time Machine: CRDT that does OT

We want the best of both worlds:

Consistency of CH merges
Abstraction of OH data
- from merge algorithm
- from other history

And very pragmatic needs:

Final updates as operations:
- To update cursors
- To update snap incrementally

... in fact, most CRDT libraries implement this OT, but don't document it!

Approach:

Encapsulate CH entirely within a peer.
- Nothing depends on it
- But compute with it, when necessary, to do merges.

What this looks like:

 - [ Trad CRDT        ]
   OH->CH----------->|Snap
   |  ------------>  |

   -[  *  *  *  * *  ]-    <--- time machine comic depiction

 - [ CRD Time Machine ]
   OH-------->CH->OH->Snap

              =[___]=      <--- encapsulated time machine comic (callout to make it big)

Let's point out key aspects:

CRDT sends CH over the network. CRDTM sends OH.
CRDT always collapses at sender's current version. CRDTM must be able to collapse at ANY version!
Both CRDT and CRDTM need to view() at receiver's current version.
- But if they want to rewind time, it's useful to read older versions too!
True CRDT only view()s current version
- CRDTM produces an op BASED ON the receiver's current version.

Putting these together, a CRDT is like a time machine that is:

split in two, from sender & receiver
each has just one button:
- collapse at current version
- incorporate & view current version
can't natively produce a delta to upgrade (but all in practice do it)

A much better time machine:

encapsulates CH within a peer
accepts ops at any version
views any version
outputs ops, not just the entire snapshot

Formalizing Time Machines

Now we formally define these concepts, to prove that a Time Machine is a generalization of OT and CRDT.

Time Machines manipulate Observed History

In Observed History, each event is described as-observed by the peer it originated at. Time Machines merge incoming observations by traveling them to the receiving peer's perspective in time.

We formally define Observed History $OH$ as the set of observations $o \in OH$ , for all known mutation events, from all peers. This form of history is called the Partial-Order Log in Baquero, and the XX in Archagon.

Observation

An observation $o$ is the tuple $(e, op, parents, version)$ , where:

Event $e$ was observed
It applies the operation $op$ to the state
At the prior version $parents$
Resulting in the version $version$

The same event can exist in multiple observations; each at a different $parents$ , displaying a potentially transformed representation of $op$ .

We also define the functions $event(o)$ , $op(o)$ , $parents(o)$ , and $version(o)$ to retrieve the corresponding elements of the tuple.

Event

An event $e$ marks a point in time, on a peer, when an edit operation occurred. You can also think of it as a “timestamp” in relative spacetime.

The set of all events in observed history form a partially-ordered causal graph, or DAG.
Each event $e$ $e$ has a set of $parents(e)$ $p a re n t s (e)$ , which is all versions immediately prior to $e$ $e$ in the causal graph.
```
       e1         Figure 1
      / \
     e2  e3
     | \ |
     e4  e5
      \ /
       e6
```
In Figure 1, $parents(e_6) = \set{e_4, e_5}$ $p a re n t s (e_{6}) = {e_{4}, e_{5}}$ .
The $frontier$ $f ro n t i er$ is the set of most-recent events—those that no other event has in its $parents$ $p a re n t s$ .
- The frontier of Figure 1 is $\set{e_6}$ .
- The frontier in Figure 2 is $\set{e_4, e_5}$ :
```
       e1        Figure 2
      / \
     e2  e3
     | \ |
     e4  e5
```

Version

We specify the $version$ $v ers i o n$ of a state by the frontier of its causal graph.
- e.g. the version in Figure 1 is $\set{e_6}$ .
- e.g. the version in Figure 2 is $\set{e_4, e_5}$ .

Merge

When we receive a new set of observed edits that represent a remote version, we merge the remote version with ours.
When we merge two versions $v_1$ and $v_2$ , we compute the state that unions all their events.
A merged version is thus $frontier(v_1 \cup v_2)$ , but we sometimes write this $v_1 \cup v_2$ as shorthand.

Operation

Each mutation occurs via some $op \in Operations$ . Different data types support different sets of $Operations$ . For instance, a counter might support:

CounterOperations = \set{\texttt{Increment(count)}, \texttt{Reset}}

Whereas, a collaborative text editor might support the operations:

TextOperations_1 = \set{\texttt{Replace(start, length, string)}}

Or it might only support explicit insertions and deletions:

TextOperations_2 = \set{\texttt{Insert(start, string)}, \texttt{Delete(start, length)}}

Additionally, we assume that there exists an operation that composes other operations, so multiple operations can be expressed as a single $op$ .

Snapshot

When we observe the state of a peer, at any point of time, we call it a “snapshot,” and refer to it as $snap$ . Operations apply to a snapshot of state, resulting in a new snapshot:

snap \bullet op = snap'

Each peer's local time progresses linearly as it applies a sequence of operations to its snapshots. Some operations are generated locally, and some are received remotely, and transformed so that they can be applied locally.

Time Machines implement View() and Travel()

A Time Machine implements two functions over observed history:

$View(OH, version) \mapsto snap$
$Travel(OH, op, from, to) \mapsto op'$

The first function, $View$ , produces the observable snapshot $snap$ at a $version$ in time. We sometimes abbreviate $View(OH) = View(OH, frontier(OH))$ . This is what a CRDT does.

The second function, $Travel(OH, op, from, to) \mapsto op'$ , transforms an operation $op$ to the equivalent $op'$ , that would be observed when the edit event travels through time from the version $from$ to the version $to$ . This is what OT does.

View() can merge

To merge a new observation $o$ using View, we simply add it to our history $OH$ and then View the result:

View(OH \cup \set{o}) = snap'

This is how a CRDT works—it reproduces the entire state with every merged edit. This makes it easier to define and guarantee consistency— you just constrain yourself to making the View function deterministic.

Travel() can merge

This is how OT works—it updates a snapshot by traveling the remote observation into our local time, and then applying it. We want this in practice because (a) re-generating a large data structure for a small edit can be inefficient, and (b) to update cursor positions and other local state annotations, we need to interpret the differential operation anyway. Practical systems need Travel.

We merge with Travel following the template $snap \bullet op' = snap'$ , where we want to produce the transformed $op'$ using our Travel function. Consider:

Send observation $o_0 = (e, op, \set{e}, parents(e))$ $o_{0} = (e, o p, {e}, p a re n t s (e))$ :
- New event $e$
- Executing $op$
- Based at version $parents(e)$
- Resulted in version $\set{e}$
Receive observation at version $v$ $v$ . The local observation of this event will be $o_v = (e, op', \set{e \cup v}, v)$ $o_{v} = (e, o p^{'}, {e \cup v}, v)$ :
- Our view of the event $e$
- Sees a transformed operation $op'$
- Based at our existing version $v$
- Resulting in a merged version $v \cup v_{remote} = v \cup \set{e}$ .
We need to compute $op'$ .
So we use $Travel(OH \cup \set{o}, op(o), parents(o), frontier(OH)) = op'$ $T r a v e l (O H \cup {o}, o p (o), p a re n t s (o), f ro n t i er (O H)) = o p^{'}$
- When we receive the remote event $o$
- We add it to $OH$ with $OH \cup \set{o}$ .
- Then Travel the $op(o)$ from the base of its $parents(o)$ to our current $frontier(OH)$ .

Now we can apply the traveled $op'$ to our $snap$ , and compute $snap'$ with:

snap \bullet Travel(OH \cup \set{o}, op(o), parents(o), frontier(OH)) = snap'

They merge equivalently because View() = snap • Travel()

If you $View$ a merger, you should see the same thing as $Traveling$ the remote $op$ to the current version as $op'$ and applying it with $snap \bullet op'$ .

View(OH \cup \set{o}) = snap \bullet Travel(OH \cup \set{o}, op(o), parents(o), frontier(OH))

Both produce the same snapshot.

We create Time Machine Objects to encapsulate history

Practical Time Machines will want to cache, hold, and encapsulate history over time. This allows them to optimize the representation of history according to their needs, by e.g. pruning old history.

So we generally define a Time Machine as an object with fields:

class TimeMachine {

field internal_history
method $Update(o)$
method $View(version) \mapsto snap$
method $Travel(op, from, to) \mapsto op'$

}

The $Update(o)$ method incorporates a new observation into the machine's internal_history, which different Time Machines might represent in different ways. The View and Travel methods draw on this history to produce snapshots and transformations.

Now the Time Machine implementation is free to represent history in new ways, such as via a collapse, without impinging on other peers' choices of representation. This e.g. lets peers prune history at different rates.

Time Machines exist throughout Computer Science

These functions can describe an array of systems in CS beyond CRDT/OT, such as MVCC in databases, event sourcing, STM, LFS, VCS, and backup systems which store and manipulate histories of operations and snapshots to implement archiving, collaboration, and parallel processing.

We differentiate a few properties here:

We say that a Time Machine:
- supports Relative time if [fill in]
- is Consistent if ... [fill in]
- has a Merge-Type of ... [fill in]
- is Differentiable if ... [fill in]
If consistent, we know:
- View() is a deterministic function
- $View(OH ∪ \set{o}) = snap \bullet Travel(OH ∪ \set{o}, op(o), parents(o), frontier(OH))$
If differentiable, we have:
- A diff function: $diff(snap_1, snap_2) = op$
- That produces a travel of observation $o = (e, op, v1, v2)$
- $View(OH ∪ \set{o}) = View(OH) \bullet Travel(OH ∪ \set{o}, op, v1, v2)$
- to do: relate delta crdts to this diff function

CRDTime Machine: a consistent View and Travel

Here's a relative, consistent time machine. It has an outer CRDT and an inner CRDT. The outer CRDT does not collapse history — it works on pure observed history. But in order to guarantee consistent merging, it encapsulates an interior collapsing CRDT $C$ that we call the collapse. Since this interior CRDT is encapsulated, each implementation is free to use instantiate it (or not) on different subsets of histories, in different ways, in different cases.

The Outer CRDT

First, we'll define the outer CRDT. This is a CRDT, as defined in Shapiro, that has four additional constraints to its definition, which allows it to simultaneously implement the Time Machine API.

So starting with the CmRDT definition from Shapiro (which he's proved is equivalent to the CvRDT definition):Since Shapiro has shown the CmRDT and CvRDT forms of CRDT equivalent, this is enough to show that we have a CRDT

(S, s^0, q, t, u, P)

We add four constraints to implement View and Travel:

All network operations are formatted as $o \in OH$
The CRDT's state is constrained to be Observed History: $S = OH$ , and $s^0 = \set{}$
The CRDT PrepareUpdate function $t$ is constrained to the identity function $t(o) \mapsto o$
The CRDT Update function $u$ $u$ does:
1. its normal thing: $OH \coloneqq OH ∪ \set{o}$
2. and now additionally returns the transform:
  $u(o) \mapsto Travel(OH ∪ \set{o}, op(o), version(o), parents(o)) = op'$

Now we have an outer CRDT that implements both View and Travel:

View is the CRDT's $read()$ or $query()$ function $q$ .
Travel is part of the of the CRDT's $update()$ function $u$ .

This defines the contract of the outer CRDT with other peers. But it does not explain how to implement $View$ and $Travel$ consistently. We will do that by defining a new internal collapsing CRDT.

The Inner Collapsing CRDT: $C$

Now we add one more term to the CmRDT: the inner “collapsing” CRDT $C$ :

(S, s^0, q, t, u, P, C)

A CRD Time Machine implements View and Travel in terms of this inner collapsing CRDT $C$ . It is not required to always use $C$ — for instance, it can skip it entirely when transforming a non-concurrent (linear) sequence of operations to obtain better performance — but it always can, and its merge-type is defined in terms of $C$ .

$C$ defines $View$ and the Merge-Type

We now constrain the Time Machine's View function in terms of the $C$ query function $q$ :

$View(OH, version) \coloneqq$ $Vi e w (O H, v ers i o n) : =$
- For each $o \in OH \cap version$ $o \in O H \cap v ers i o n$
  - call $C.u(o)$
- return $C.q()$

This defines the merge-type.

Defining Travel is the remaining challenge

Now, we have to implement Travel.
There is some freedom in doing so.
We need two things:
- Consistently updating a snapshot with a delta
- Updating cursor positions and other local annotations

TP0 guarantees consistent Travel in CRDTime Machine

In order to be Consistent, we need View and Travel to be consistent. Well, View will be consistent as long as it is deterministic. That is easy to do. If we have that, we can define Travel's consistency in terms of View. We can do that with the equivalence property from before:

snap_1 \bullet op' = snap_2

Given a Travel() function outputting $op'$ for any merged version, TP0 is true iff applying the $op'$ to any $snap_1$ produces a $snap_2$ , that's equivalent to the snapshots produced by View() at versions $v_1$ and $v_2$ .

\begin{alignat}{3} snap_1 &\bullet &op' &= &snap_2\\ View(OH, v_1) &\bullet &Travel(OH, op, v_1, v_2) &= &View(OH, v2) \end{alignat}

TP0 verifies consistency of merges

A great way to test your system for TP0 is to see if it is satisfied for every possible merge, given some observation $o$ to merge into a base version $v$ .

We know that:

history starts at $OH$ and then becomes $OH \cup \set{o}$
$v_1 = v$
$v_2 = v \cup version(o)$
$op = op(o)$

So we can now express TP0 in terms of View and Travel when merging $o$ at $v$ :

TP0 \iff View(OH ∪ \set{o}) = View(OH) \bullet Travel(OH \cup \set{o}, op(o), parents(o), frontier(OH))

Any differential CRDT can satisfy TP0

TP0 allows ambiguous travels

There are often multiple possible $op'$ to go from $snap_1$ to $snap_2$ . For instance, the string mutation "XX" $\to$ "XXX" could be achieved by inserting an "X" at any of positions 0, 1, or 2; or even by replacing characters 1 or 2 with the two-byte string "XX".

Example: the $diff(snap_1, snap_2) \mapsto op'$ function satisfies TP0.

TP0 is different from TP1 and TP2.

TP0 guarantees that a peer's local snapshot updates consistently from Travel's transformed operations. This is all you need to prove that your snapshot-update satisfies Strong Eventual Consistency (SEC), and thus is a CRDT.

Updating cursor locations and annotations with TP½

Surprise, this turns out to be equivalent to TP1 and TP2.

[Todo: incorporate from meeting 77]

The Big Picture: what is CRDT and OT?

Thus, far from OT and CRDT being separate, we will show that not only is a CTM a CRDT, and an OT implementation, but it is also implemented using an internal CRDT, and sometimes with internal OT, which runs top of a history that is itself a CRDT, and can be generated by OT.

     Observed         Observable         Observed
     @ Peer 1         @ Sender           @ Peer 2

         o                o                 o         time
         |               / \                |         |
         o              o   o               o         V
         |              | / |               |
         o              o   o               o
         |               \ /                |
         o                o                 o

                    - Collapse(H) -
                          v
                         (*)

    | Sending Peer    |       | Receiving Peer  |
    | State   | Edit  |  TM   | Rebased | State |
    |---------|-------|-------|---------|-------|
    |         |       |       |         |       |
              |------>|                           this is a trivial crdt
                      |------>|                   this is a crdt
                      |------------------------>| this is a crdt too

                      |------>|                   this can be done with OT TP1, TP2
                      |---------------->|         ""   <-- maybe it should be this
                              |-------->|         this can be done with OT TP0
                      |---------------->|         this is OT

Figure 4.4

We hope the reader can dispel the notion that CRDTs and OTs are competing algorithms. They are rather complementary properties of algorithms that we can strive to implement together within our Time Machines.

Figure 4.4 (above) depicts the flow of information within a Collapsing Time Machine. (Acknowledge Seph.)

Todo: proofs & explanations of each line

$OH$ is a CRDT
$C$ is a CRDT
The Time Machine is a CRDT
$C$ can be implemented with OT (TP1, TP2)
Travel() is OT
Travel() can be implemented by a TP0 diff on $C$ $C$
- [ to do: relate delta CRDTs to this diff function ]

$\therefore$ A CRD Time Machine is a CRDT that does OT through a CRDT.

Example Time Machines

Braid-HTTP: standard protocol

Supports any known CRDT/OT algo as collapse (currently by wrapping w/ TP0 diff)
TM provides key standard ability -- which BTW we've taken further by solving two other major issues in standardization:
- Even has a standard format for operations -- range-patch, which, when extended with a "portal", can cover all patch types of known CRDT & OT systems.
- Reference-crdts proves we can abstract the merge-type for text editing CRDTs as two functions over a space DAG to maintain a topological sort order

Sync9 + Antimatter: prune all history

Sync9 is a CRD Time Machine
- But slow O(size(OH)) behavior — knowing that we can prune OH!
Antimatter sends extra messages over P2P network to discern what can be pruned
- Fully distributed algo
- Arbitrary connections, disconnects, reconnects
- Each peer only knows:
  - immediate neighbors O(p)
  - partition events (called fissures) O(p)
  - No peer knows the whole network.
- Guarantees consistency
- Prunes down to 0 overhead when reconnected

Sync7 and DT merge over subset of history

Sync7
- Operated on only subset of history since fork point
- But was slow (like $O(n^3)$ or $O(n^4)$ ) on that subset
DT
- Fast, practical, very useful
  - Performance is better than state of the art
  - Degrades to polynomial only in rare case
- Most edits are non-concurrent, or simple
  - And can be done without history, or with much less history in ram

Enables Memory Hierarchies

DT and Antimatter Illustrate levels of memory
- Some can be on disk, only loaded when necessary
- Some can be stored, but pruned from a clique that cares about each other
- Others can be loaded over a standard protocol Braid-HTTP
  - [ example Braid-HTTP request and response to archive node ]

DiffSync: a VCS-style implementation

You can also merge in radically different ways
Implements Git's recursive 3-way merge
All edits still in pure OH
This has issues of ambiguous diffing -- (Q: can that lead to inconsistency, e.g. when used with pruning?)

Simpleton: easier implementation

TP0 over the network, for any CRDT, to a light client
Only 70 lines of client code
Guarantees consistency in exchange for half-duplex bandwidth
Specification only needs a merge-type
Standard vocab -- compatible versions and snapshots
- Can even upgrade a system in-place, adding extra information later, to make additional sense of existing versions, and snapshots!

Modular History

Observed history is capable of replacing a span of history as a module with an equivalent module, without affecting the key properties of:

View()
Transform()

Examples of what we'll achieve

Merging from a subset of history (e.g. summarize everything before a fork point)
Pruning history as a summary
Requesting summaries of history

Peers can do this in order to:

Tame the CRDT history blowup problem
- Takes up space on disk
- Operations can traverse smaller history
Without affecting other peers
- Peers can hold different, but compatible, representations of history, and still sync the same
Without changing the network format
- Intermediaries can still support various modules
Requesting special history in light clients
- Receiving modules of forgotten history
- Receiving simplified (rebased) history
- Receiving pre-merged snapshots

And they can do it differently on each peer, and even change behaviors over time — all without breaking compatibility and consistency.

We can replace a span of history with an alternate subgraph of events.

Summarize(OH, from, to) \mapsto Subgraph

Summaries are generated by a set of functions applicable to a CRDTM defined by Semantics = (Ops, View). Each function has a set of properties for that CRDTM:

Applicable Time Domain of View() & Travel()
View equivalence at View(OH, to(w))
TP0 and TP1/2 of Travel(OH, op, from, to)

Examples $Summarize : OH \to OH$ functions:

MAX registers that summarize to (value):
Counters that summarize to (value):
LWW registers that summarize to (version_seq, val):
- Span: any connected subgraph, including the whole thing from root to frontier
- Range of View(): internal: none, external: full.
- Domain and range of Travel(): full
- Example situation of use: after each update, replace full history
Summarize WithinBubble in DT/Sync9:
- [ draw picture ]
- "Traveling in text doesn't need information within bubbles that are non-overlapping with from or to"
- Span: within a bubble of time
- Range of View():
  - Internal: none
  - External: all
- Domain & Range of Travel():
  - Internal: none
  - External: all
- EXAMPLE USE: prune history when no versions will come from within a bubble
Summarize OutOfBubble in DT/Sync9:
- "Traveling in text only needs to info within the smallest bubble containing from and to"
- Span: before and after a bubble
- Range of View():
  - Internal: all
  - External: none
- Domain & Range of Travel():
  - Internal: all
  - External: none
- EXAMPLE USE: load just a subset of history into memory to compute a Travel
Summarize BeforeForkPoint in Stable CRDT:
- "Traveling a stable CRDT doesn't need info before the fork point"
- Span: before forkpoint
- Range of View:
  - Internal: none
  - External

And all these can interoperate.

Rebasing peers, next to fully p2p peers
They all can compute the same versions, and switch behavior, working off snapshots

CRDT and OT generalize as Time Machines