Branching and Merging

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.

Subscribe to RSS - Branching and Merging