Wave Protocol

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.

Google Wave: Operational Transform and Server Acknowledgements

Google Wave is an exciting new product from Google that aims to become a communications hub, replacing many current communication types, including email, instant messaging, blogging and wiki. By encompassing the features of all of these systems, a single unified system can be used for all of these communication styles.

If you have not heard of Google Wave then the presentations given at Google IO 2009 are a great place to start to understand what it is all about:

Subscribe to RSS - Wave Protocol