Google Wave: Intention Preservation, Branching, Merging and TP2

Operational Transformation (OT) is hitting the mainstream thanks to Google Wave. The Wave Protocol uses OT as the basis for communication between clients and servers.

There are two properties required of OT algorithms in order to ensure consistency. In the literature these are called Transformation Property 1 and Transformation Property 2, or TP1 and TP2. Satisfying TP1 is required to guarantee convergence for two sites that apply concurrent operations in different orders. Satisfying TP1 and TP2 is required to guarantee convergence for any number of sites that apply concurrent operations in different orders.

Satisfying TP2 is hard! In fact, almost all published algorithms that claim to satisfy TP2 have been shown to be flawed. However, there is an alternative; it is possible to constrain the communication between multiple users in a manner that allows any number of users to concurrently edit a document, synchronize using OT and still converge while only satisfying TP1. The secret is to use a centralised server to make the communication look like n two-way collaborations rather than a single n-way collaboration where n is the number of users. The idea was published in the Jupiter Collaboration System and forms the basis of the Wave Protocol.

For a little background reading, the fellows at Coralius discussed the Wave Protocol and TP2 in their blog.

However, guaranteeing convergence is not the be-all and end-all of OT. In this article I will examine Intention Preservation and Concurrent Revision Control (Branching and Merging) for OT systems that do not satisfy TP2.

Intention Preservation

In the Wikipedia article, Intention preservation is defined as follows:

  1. Intention Preservation: ensures that the effect of executing an operation on any document state be the same as
  2. the intention of the operation. The intention of an operation O is defined as the execution effect which can be
  3. achieved by applying O on the document state from which O was generated.

Basically, Intention Preservation means that a given operation should do what the user intended regardless of the transformations it goes through or which document state it is applied to. Preserving the users intention can be difficult; in fact, defining what the users intention actually is can be difficult! There are formal definitions for Intention Preservation, such as the work by Du Li and Rui Li where the Effects Relation is defined, however, I will be a somewhat less formal and rely on intuition to show an example where the users intention is not preserved due to a lack of TP2 support.

Let's say that when a user inserts B after X for a given document "XY", then the user means "Insert B after X and before Y and after all other characters inserted before X and before all other characters inserted after Y". This is the intent of the user and it should be preserved.

Consider the following scenario. There is a document whose current state is "X". Three clients concurrently generate operations against this document as follows:

  1. Client 1: insert "A" before the "X"
  2. Client 2: insert "B" after the "X"
  3. Client 3: delete the "X"

I'm sure that everyone will agree that the final document state after all sites receive, transform and apply all operations must be "AB" if the intention of the users is to be preserved. However, this is not what necessarily happens in Wave.

There are six possible orders that the Wave server could apply these operations and two of them may give unexpected results! If the server decided to apply delete operation first, then the two inserts, once transformed to include the effect of the delete, will appear to be concurrent inserts at the same position. In the literature, the site identifier is used to break this tie, meaning that half the time the result final state will "AB" and half the time it will be "BA". Wave doesn't use site identifiers, but rather, relies on the order that the server chooses for these inserts - this still leads to "BA" half the time.

What is described above is a classic TP2 puzzle. In a peer-to-peer OT system this would represent divergence amongst peers (which is why a peer-to-peer OT system must satisfy TP2). In Wave it just gives a plain weird result which I see it as not preserving the intention of the users.

Branching and Merging

Software engineers have used Concurrent Revision Control systems such as CVS, Subversion, GIT and Clear Case for decades. The ability to maintain divergent copies of documents (called branching) and later merge these copies is very important to support multiple software releases concurrently. However, the concepts of branching and merging are not confined to Software Development - ever used track changes in Word? That's a form of branching and merging!

OT systems should be the king of Concurrent Revision Control. There is no need for generating diffs from final document states, there is no "merge conflict" when edits fall on the same line, branching and merging of binary data is possible, and so on. However, if TP2 is not satisfied, then arbitrary branching and merging is not possible. This is demonstrated in the example below, which builds on the TP2 Puzzle shown above.

Let's define branching as maintaining multiple streams of operations that stem from the some common point in the history of operations recorded by the server. For example, if the server's history is:

  1. [O1, O2, O3, O4, O5, O6]

Then I might branch from O3 and generate Oa, Ob and Oc. Now the server's history of operations is like the following:

  1. [O4, O5, O6] (branch 1)
  2. /
  3. [O1, O2, O3] (common prefix of both branches)
  4. \
  5. [Oa, Ob, Oc] (branch 2)
  8. Ocommon = [O1, O2, O3]
  9. B1 = Ocommon + [O4, O5, O6]
  10. B2 = Ocommon + [Oa, Ob, Oc]

In terms of OT, the operations O4, O5 and O6 appear to be concurrent with respect to Oa, Ob and Oc.

Let's define a pair-wise merge of B2 onto B1 to be B1 plus the operations from B2 less the common prefix. Of course, the operations from B2 need to be transformed as part of this merge. For example, merging B2 onto B1 would result in:

  1. [O1, O2, O3, O4, O5, O6, Oa', Ob', Oc']
  2. where [Oa', Ob', Oc'] = IT( [Oa, Ob, Oc], [O4, O5, O6] )

Note that if we instead merge B1 onto B2, we will get operations in different orders:

  1. [O1, O2, O3, Oa, Ob, Oc, O4', O5', O6']
  2. where [O4', O5', O6'] = IT( [O4, O5, O6], [Oa, Ob, Oc] )

Let's emulate the TP2 puzzle that I noted in an earlier message, but this time using branches rather than clients generate concurrent operations. Let's start with a document whose state is "X" and create three branches and generate one operation on each branch (note that the common prefix is empty, so we can drop it from the above equations for the sake of simplicity).

  1. B1 = [O1] O1 deletes the "X"
  2. B2 = [O2] O2 inserts "A" before the "X"
  3. B3 = [O3] O3 inserts "B" after the "X"

If we wanted to merge all three branches together, then we need to perform two pair-wise merges. For example, merge B1 onto B2 to form a new branch (which we will call B4) and then merge B3 onto B4:

  1. B4 = merge( B1, B2 ) = [ O2, O1' ]
  2. B5 = merge( B3, B4 ) = [ O2, O1', O3' ]

B5 is the final merged result. More concisely, we can write this as:

  1. merge( B3, merge( B1, B2 ) ) = [ O2, O1', O3' ]

There are 12 possible pair-wise merges that can be done in order to merge all three branches together. All of these merges must provide the the same final document state. However, just like in the TP2 puzzle, there are some mergings that may give an erroneous result if TP2 is not satisfied. For example, consider the following:

  1. merge( B3, merge( B2, B1 ) ) = [O1, O2', O3'], and
  2. merge( B2, merge( B3, B1 ) ) = [O1, O3'', O2'']

As described previously when talking about the TP2 puzzle, the two transformed inserts appear to be at the same position. Breaking this tie can lead to producing either "AB" or "BA" as the final document state. This ambiguity leads to divergence between branches where no divergence should occur. Of course, if the OT functions satisfied TP2, then no divergence would occur. Note that this is irrespective of whether a client/server architecture is used or not.

The Wrap Up

By not satisfying TP2, Wave has some limitations that might not be expected. Who would have thought that this strange problem with Intention Preservation would have existed? Can Wave support Branching and Merging, albeit in a constrained form? Perhaps these limitations are not important. My feeling is that the problems listed here are just the start of a long list of problems with Wave for which satisfying TP2 is the right answer - but that's a story for another day.