Eventual Consistency

subtitle: (celebrating 50 years of collaborative grocery lists)

NB: 90% complete, sections are made for convenience of editing and might not be useful for the publication

prologue: got milk? (1968)

Got milk? (1968)

A now canonized moment in many tellings of the history of computation is the so-called Mother of all demos when Douglas Engelbart and a team of (student) engineers performed a kind of technical theater at a technical computer conference in San Francisco in 1968. In the demo, Engelbart sits in front of computer display and proceeds to use something that (to a modern eye) seems to fuse elements of a text editor, outliner, drawing program, and web browser. At one point he begins to prepare a grocery list starting with a flat list of items needed, then proceeding to show off the systems ability to category and display the list in a variety of orders and eventually even produces a graphical optimal route to go home to complete his to dos. At some point (through a bit of stage magic using then state of the art video screen splitting equipment), Engelbart appears to initiate a kind of video conference with a colleague at a remote location and the two proceed to edit some computer code together.

The wikipedia article Collaborative real-time editor was first created by user MattisManzel May 30 2005 , and initially listed just two software examples: SubEthaEdit and MoonEdit. On November 19 2008, a link is added to a new wikipedia page (also created that day) called Etherpad. A reference to Douglas Engelbart and the “mother of all demos” is later added on December 7, 2009. Despite getting marked as vandalism and removed the same day, the reference returns the 20th of December where it has remained until today.

etherpad

This essay started as a research into the algorithms underlying the Etherpad application, a browser-based collaborative text editor that has become central to many practices around Constant, (a Brussels-based arts and new media organization …). In my shared role as a Constant system administrator, and as a participant in the Diversions working session, I have developed a somewhat intimate relationship to this software object. The particularities of the software, and the centrality of its role to the much of the collaborative work around Constant, has significantly driven my own (and others around me) software practices. The necessity to manage problems such as etherpad’s ever-growing (and eventually unmanageably large) database size as well as the need to provide continuous access to documents given the server’s (and related ecosystem of plugins) often unstable nature has led to the development of scripts to manage static snapshots of etherpad content. Similarly, the software’s high demands on network connectivity when collaborating with a large numbers of users working together in the same (physical) place led to extensive thinking about and software development for local/portable infrastructures.

If you want to find out how Etherpad’s Easysync works (the library that makes it really realtime), start with this PDF (complex, but worth reading).

My explorations started in the Etherpad documentation, my interest piqued by that phrase complex but worth reading that appears in the README of the project’s source code. This led, in typical web fashion, to a mesh of interlinking (video) presentations and academic papers describing algorithms and techniques around collaborative (digital) writing systems. Two particular algorithms were repeatedly invoked and appeared central to this research: the operational transformation (OT) and the conflict-free replicated data type (CRDT).

David Greenspan, one of the original developers of Etherpad (and presumably an author of that complex, but worth reading PDF document), gave a helpful presentation at a special “Etherpad Meetup” in San Francisco in 2013 providing a technical description of Operational Transformation situated in the particular history of the etherpad project. Greenspan starts his presentation by describing his current work for a startup web-framework project. Etherpad was itself born from another web framework called AppJet, a project Greenspan co-founded with two ex-Google engineers in 2007 to push the limits of applications based on a browser/server infrastructure rather working in isolatation like most traditional (offline) PC software. In mid 2008 he writes an email to colleagues proposing that they should try to build a cross between superhappychat (another early AppJet prototype) and SubEthaEdit (a Mac-based collaborative editor) where “merging should be done to an extent that people can comfortably co-edit a document, and perhaps text could be colored by author.”. The project is announced publically just months later, on November 19.

Documents

• A document is a list of characters, or a string.
• A document can also be represented as a list of changesets.

Changesets

• A changeset represents a change to a document.
• A changeset can be applied to a document to produce a new document.

Greenspan proceeds to describe how etherpad documents are based on the concept of changesets – a concept he claims he “developed as the result of an all-nighter”. Changesets are a concise representation of just the changes an author makes to a particular text. For instance, if on were to type the following into etherpad:

this
is
a
text

And then change the last word from “text” to “test”, the complete document as a list of changesets would be:

Changeset               Interpretation
--------------------    --------------------
Z:1>3*0+3$thi           insert 3 characters: thi
Z:4>2=3*0|1+2$s\n       keep 3 chars, insert 1 line: s (newline)
Z:6>2|1=5*0+2$is        keep 1 line, insert 2 characters: is
Z:8>1|1=5=2*0|1+1$\n    keep 1 line, keep 2 characters, insert (newline) 
Z:9>2|2=8*0|1+2$a\n     keep 2 lines, insert 1 line: a (newline)
Z:b>2|3=a*0+2$te        keep 3 lines, insert 2 characters: te
Z:d>2|3=a=2*0+2$xt      keep 3 lines, keep 2 characters, insert xt
Z:f<1|3=a=2-1$          keep 3 lines, keep 2 characters, delete 1 character
Z:e>1|3=a=2*0+1$s       keep 3 lines, keep 2 characters, insert 1 character: s

Representing the “document as list of changesets” has something in common with a wikipedia article, where internally, a database is used to record the entire history of changes editors have made. In this way, it’s possible to view the entire timeline of edits, view differences between those edits, and eventually make “reversions” to previously written formulations or remove unwanted edits. In the case of wikipedia, the granularity of this history is each time an editor saves a version. In the case of etherpad, the granularity of editing is much finer, often reducing edits to a few keystrokes that in effect are automatically committed as each editor types. As each changeset is considered a “revision” it is usual for a document to have tens of thousands of revisions. Combined with the added overhead that each changeset also is timestamped and associated with an author, makes the seamingly compact representation grow to potentially unmanageable database sizes when used for a long period of time with many pads and authors.

While the design of the changeset representation and accompanying easysync algorithm is not for compactness it is instead for the speed of distributing these changes to other authors and for automatically merging different editors contributions. To demonstrate this, Greenspan gives the example of the text “Here is a very nice sentence” changed by two editors simultaneously into: “Here is a sentence” and “I like a nice sentence”. The goal of easysync is to combine or merge these two edits into a shared common version.

caption Two editors divergent edits are merged

In the slide red cross-outs (deletions) and the green additions (insertions) show the changesets. The merge algorithm is designed to honor both editors’ deletions, then performs both of their insertions. In this case, the resulting merged sentence is “HereI like a sentence.”. Any user of etherpad will recognize the multi-colored formatting of the final sentence, with the two authors voices spliced together like wedges of neapolitan ice cream (each assigned a distinct color). Also familar would be the way using the software involves moments of rupture, where collectively written texts often temporarily break, or swell with duplications to then be resutured or whittled down in the process of further editing. The important point is that the software doesn’t so much choose a final version of the text, but rather the merging happens quickly enough to catalyze a social process of negotiation to an eventual correction or reworking of a text. Greenspan, for his part, is cognisant of this, and at one point reminds the audience that the algorithm is really only good for merging changes made in a very short time span (something on the order 30 seconds). The merging is purely to manage the kind of real or near real time conflicts where both editors are assumed present and actively engaged with the text. Using the algorithm to merge changes made by independent editing made out of the context of this live social negotiation simply wouldn’t make sense.

Greenspan later dives into the concept of the “Operational Transformation” – the larger algorithm etherpad uses to synchronize the activities of many editors in (near) real time. In order to zoom into the algorithm, Greenspan pares back the edits to an even simpler moment where the text “Hello” is again edited simultaneously to “Hello!” and “Yellow”. He shows a series of diagrams where the two edits are represented as change vectors extending from a common starting point to two points of divergence (opposite corners of the diagram). The key idea of OT is how changes are exchanged and transformed among editors so that changes made by others can be (sensibly) applied to the one’s own local (and often changed) context. In other words, editor 2 will transform editor one’s exclamation point to add it to their edit Yellow, while editor one will receive editor 2’s “Y” and “w” and apply that to their edit “Hello!”. Ultimately, in addition to being design to be efficient, the goal is for the result of all the transformations to converge – that is produce the same final text. Thus OT “squares” the diagram with the result of the transformed transformations (in principle) returning back to a shared state.

CRDT

In a 2018 presentation, researcher Martin Kleppman describes an alternative technique to OT called Conflict-free replicated data type (CRDT). Kleppman begins his presentation introducing a generalized idea of “collaborative applications” and starts with an example that would be familiar to his technical audience, that of programmers commiting code with git, the popular distributed version control system.

Hello World! :-)

He then moves to a “textual” example nearly identical to Greenspan, again showing two simple parallel edits merged into one. As in etherpad, the edits are shown as arrows from one text to another and labelled as “transformations” (insert “world” after “hello”). Here, Kleppman notes that this is indeed the way that “Google Docs” work. Though Kleppman never refers to etherpad, the points he makes are valid to both as each is in fact based on the same OT-based model.

Ordered List CRDT

Kleppman then goes on to draw a line between OT and a more recently developed concept, that of the Conflict-free replicated data type (CRDT). Kleppman, a researcher in distributed systems at the University of Cambridge, reminds his audience that OT, though originating in 1989, and implmented in a number of projects, has a checkered academic history with parts of its theories later disproven. In particular, many “edge cases” have been demonstrated where diverging edits will not converge under certain forms of OT. He notes how the particular algorithm employed by Google Docs (and etherpad as well) works only because it relies upon a single centralized server to ensure for a consistent shared state. This, he notes, has serious consequences such as preventing say a mobile phone to synchronize data directly with a nearby laptop; indeed Google docs requires both devices to contact a “cloud server” in a data center, a situation that seems grounded in this particular flaw of the OT implementation.

Inserting in the same place

The CRDT models Kleppman presents, in contrast, have been subject to rigorous formal testing and shown to demonstrate a property that the academic literature terms “Strong Eventual Consistency” – a guantee that given enough time for messages from each editor to circulate to other editors, each document is guaranteed to arrive at the same resulting document state. Thus CRDTs (at least theoretically) seem better able to exploit a potentially more radical peer to peer network infrastructure.

1 + 1 = 3?

Part of Kleppman’s aim in describing CRDTs is to describe the generality of the technique and indeed the multiplicity of possible DTs or data types. Klepman’s “Hello World” slide is in fact followed by two other examples of “collaborative editing”. One shows that instead of text, editors might be editing sets ( {a, b} ) with one editor removing element {b} and another adding element {c} and the algorithm seamlessly merges these to {a, c}. The final example is one that often appears in discussions of CRDTs as the simplest of cases: a “counter”. Here the two editors are shown with an initial state that says “c = 1”. Arrows are then shown labelled “increment” transforming the “text” into “c = 2”. Kleppman notes here that you might be tempted to say that both editors are in agreement with c = 2, but that this would in fact “lose information”. Instead, he shows how that when two edits are then merged, both editors arrive at the final state “c = 3”. To support this he further explain:

We need to consider not just the state – the value at any one time – because if we compare just 2 and 2 they look the same, but actually we need to capture the sequence of changes that were made to the data and re-apply those, and that will allow us to reach a sensible merged outcome.

Here Kleppman significantly makes a shift from text to data, with edits becoming changes to the data, that presumably are unambiguous and thus can be “sensibly” merged with the precision of a logical operation.

In a textual sense, what exactly is meant with two authors write c + 1 = 2 depends on the context. If they were transcribing an algebra lecture, the repetition may indeed simply be that, an insistence upon the fact that c = 2 is indeed what was said. But even if one accepts the shift from “textual state” to “data”, the question of context remains. If indeed the “incrementer” is a “like counter” then indeed doubly incrementing makes sense, but instead if the editors are collectively counting (in drinking-game style) the number of times a speaker uses a certain word, then c=3 would represent a double count.

Kleppman’s theoretical precision obscures a lack of consideration of any role the social context around the systems might in fact play a role in assessing the qualities of “collaboration” possible in such a system. While Greenspan makes referance to the fact that any kind of “auto merge” algorithm necessarily involves questions of “preserving intention”, Kleppman falls more or less into the trap of the evident clarity of precisely defined data structures. When Greenspan’s describes a “weird case” of two editors simultaeously deleting then editing opposing halves of text and notes that the algorithm is “guaranteed to look weird, but also guaranteed to work”, he’s assuming that editors are engaged with each other in the realtime loop of the editor and thus are likely to stop and negotiate. In contrast, when Kleppman at the end of his talk moves to describing a practical implementation of CRDTs it in a system called “automerge”, and the example a shopping list. XXXXXXXXXXXXXXX todo: make a point here ?

neats vs. scruffies

Friction between engineers formally defined systems, and the messy realties of (collaborative) writing practices. Is this just another case of neats vs. scruffies with Greenspan’s scruffy acceptance of the messiness of social process reflected in a lack of theoretical precision, or does Kleppman’s neat precision indeed obscure a dangerous lack of interest in the actual qualities of collaboration present, despite the logical correctness of their data structures.

Raph Levien’s unified theory of OT and CRDT

( CUT??? It’s important to note though that here too, what the “correct” behavior is depends on the situation of use. For example, using etherpad to collectively transcribe a live event – a situation often used during Constant working sessions – it often arises that two people type duplications of the same text. Etherpads behaviour, which despite its flaws in determinism, also merges the disparate changes by including both versions of the text leads to the result that in this situation, the desire to produce a “clean” transcription results in one of the two authors needing to notice the duplication and choosing to delete either their own or the others input. It is conceivable, that a different modality of a merge algorithm might instead align the two editors contributions and instead perhaps highlight or emphasize the portions typed by both (thus reinforcing a kind of “insistence” rather than “repetition”). )

epilogue: collaborative technotexts

Technotexts: When a literary work interrogates the inscription technology that produces it, it mobilizes relexive oos between its imaginative world and the material apparatus embodying that creatin as a physical presence.

TODO: epilogue: two alternative examples of “collaborative writing sytems” that function as “techno texts” (Hayles), making use of the particularity of their materiality.

• Your world of text … (simple character based level of conflict resolution – graffiti conflicts) – also anonymity ;; lots of racist / dicks etc. (without any care)
• Epicpedia, Annemieke van der Hoek (2008) (care community of wikipedia – exposing the underlying structure obscured by the wikipedia interface)

• 

  Your World of Text, Andrew Badr (2009)

• 
• 

  Epicpedia, Annemieke van der Hoek (2008)

• 
• 
•