Hi, my name is Geoffrey Litt, and I'll be presenting joint work done
with Sarah Lim, Martin Kleppmann and Peter van Hardenberg, supported by the
industrial research lab Ink and Switch.
I'll be telling you about Peritext, a novel algorithm for mediating
collaboration over rich text documents.
These days, rich text collaboration is everywhere.
We all use tools like Google docs as part of knowledge work.
And these tools don't operate on plain text.
They operate on rich text, which includes things like bold and
italics and other formatting.
Now these tools and interfaces for writing rest on top of
distributed systems algorithms.
These algorithms help ensure correctness in the collaborative editing process.
And they also help define the kinds of collaboration that are
even possible to begin with.
A key challenge in collaborative editing tools is how to handle
concurrent editing, when multiple people edit the same document without
having seen each others' changes.
And in these scenarios, there are two important properties
that we want to preserve.
The first is strong eventual consistency.
Everyone should eventually end up seeing the same state of the
document on their respective devices.
The second property is a more nebulous one.
It's the idea of intent preservation.
Here we mean that the shared state everyone converges to
should somehow be reasonable.
It should reflect a faithful merge of the intentions of the original edits.
Let's look at an example of intent preservation in the domain of plain text.
Let's say we start with a sentence "the fox jumped" and two users concurrently
insert different words in the sentence.
One inserts "quick", the other inserts "brown".
What should the final result be once we merge back together?
One result we could imagine is something like this, where all the
letters get combined in some order.
But this is a difficult result to work with and edit later because the two words
have become interleaved with each other.
So we can say that this is a failure of intent preservation in some sense.
A better merge result might be something like this, putting the individual
words that were inserted separately so that we can edit from there.
A key contribution of our work in Peritext is extending these ideas of
intent preservation properties from plain text to rich text with formatting.
For example, consider this sentence from before and this time, Alice
bolds the entire sentence and Bob inserts the word brown.
What should happen when these two results merge together?
You might say that we should end up with something like this, where the words
that Alice bolded have become bold and the newly inserted word is not bold.
But this seems like a sort of strange result because it seems
like Alice's intention wasn't to bold those individual words.
It was to bold the entire sentence.
A better result might be something like this where the entire sentence, including
the newly inserted word has been bolded.
And this is the result that we propose as intent preserving in our work.
Let's consider another example where two users concurrently apply
formatting to the same document.
Here, Alice bolds these two words and Bob italicizes these two words.
In this case, the merge result is pretty straightforward: because bold
and italic can both exist on the same characters, we can have the middle
word Fox be both bold and italic.
Now let's consider another example of concurrent formatting.
In this case.
Alice sets these words to red and Bob sets these words to blue.
The problem is when we merge now, we can't set the middle
word Fox to be both red and blue.
We propose that the best solution here is just to pick one of
those colors arbitrarily as the color for the overlapping word.
Our paper has more examples like this to illustrate our proposed specification for
intent preservation in rich text editing.
Next let's explore some of the solutions that are possible for
satisfying these specifications.
A popular class of approaches is known as operational transform or OT.
And the basic idea there is that we transform operations relative to each
other, to account for concurrent editing.
For example, we might adjust numeric indexes of insertions to account
for other concurrent insertions.
There are multiple commercial implementations of OT for rich
text which support products like Google docs and word 365.
However, there are some drawbacks to the OT approach.
A major drawback is that all the known rich text OT algorithms that correctly
converge require a central server.
This can limit the scalability of an algorithm.
It also prohibits decentralized editing workflows and limits the
ability to apply end-to-end encryption.
Another drawback of OT is that it's designed for a particular
kind of editing workflow.
Where there's one main document and edits are being applied to that
shared document as soon as possible.
OT isn't designed for more flexible branching and merging workflows
where there can be many versions of a documents simultaneously, and they can
be merged into each other at any time.
Finally OT can be complex to implement because it requires a
different transformation function for every pair of operation types.
A different class of approaches is known as conflict free
replicated data types or a CRDTs.
And the key idea here is to model operations in a
fundamentally commutative way.
So we avoid the need to transform operations relative to each other.
And CRDTs can have good support for decentralized and offline editing
workflows and can support more flexible merging and branching workflows.
Like the ones I was just mentioning.
However, while there's many plaintext CRDTs, there's not been
much work on rich tech CRDTs.
There's no published academic work on the subject.
Let's take a look at how CRDTs for plaintext sequences work.
Typically they assign IDs to individual characters in the
sequence like these shown here.
And then our operations for inserting characters happen relative to those IDs.
For example, if you want to insert the letter X here, instead of giving a numeric
insertion index, we say, after this ID.
Another key idea is that instead of deleting characters entirely
from the sequence, we can use tombstone flags to model deletions.
And you might ask, can we just add some simple extensions to
these existing plaintext CRDTs to enable them to support rich text?
For example, you could add inline control characters, like HTML
tags into the plain text sequence.
However we show in our paper that these kinds of simple extensions actually
fail to preserve intent the way we want.
And that brings us to our proposed algorithm , Peritext.
We do extend the plaintext CRDT in Peritext, but in a very
particular way that ensures intent preservation and convergence..
A first key idea is that we maintain a set of formatting operations
alongside the plaintext sequence.
For example, here we have an operation to add bolding to part of the sequence.
The operations start and end on either side of these characters.
You can see here that this operation is attached to these particular
characters in the sequence.
It's also very important that the set of formatting operations only grows.
So when we remove formatting, we don't remove operations.
Instead we add more operations to represent removing formatting.
A second key idea is that we can deterministically derive a state
of the formatted document from the plaintext sequence and our
set of formatting operations.
The basic idea is to iterate over the document from left to right, and look
at which operations are active in each region of the document and add them all
together to arrive at the formatting for that particular span of the document.
In the paper, we describe more details of how exactly this works,
and how we can make it efficient.
A final detail is considering what happens when different
operations conflict with each other.
For example, here we have an operation to add bold and remove bold formatting
on the same span of the document.
In these cases, we use a standard last-writer-wins conflict resolution
strategy which means that we can compare logical timestamps between
these operations to pick one of them to win deterministically
across all of our replicas.
That's all I have time for for now.
Thanks so much for listening.
You can see our paper for a fuller specification of intent
preservation, pseudocode and TypeScript code for our algorithm
and a formal proof that it converges.
And you can see more information at this URL right here.
Thanks so much.