Operational Transform

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.

Introducing CEDA - a platform for collaboration

Today I am pleased to announce the first in a series of white papers that talk about CEDA. What is CEDA? Well, that's exactly what the first paper is about! The abstract of the Introducing CEDA white paper is reproduced below:

CEDA is a high performance database technology that uses Operational Transformation (OT) to support replication and synchronisation for collaborative data entry performed by multiple users. CEDA is an ideal platform for Computer Supported Collaborative Work (CSCW), allowing multiple users to edit that same data concurrently. Users can collaborate in a interactive, realtime manner or work offline and control when changes are propagated to/from other users.

CEDA provides an application development platform for building applications that support collaborative work. Application developers can easily build multiuser applications based on CEDA that are as responsive as single user applications while attaining benefits of realtime interactive collaboration and sophisticated version control. The platform allows for branching and merging of the entire database, supporting manual check-ins, check-outs, updates, tagging and so forth in a similar manner to source code repository systems like ClearCase and Subversion.

The OT algorithms employed by CEDA are extraordinarily efficient, allowing users to work off line for long periods of time and then quickly synchronise with other users.

This paper provides an introduction to CEDA and some of the platforms features.

Think Bottom Up staff have been involved in the research and development of CEDA for the last 12 years or so, though the original research by David Barrett-Lennard goes back further than that. We are very excited about CEDA and the potential of the technology. The collaborative features of CEDA are achieved through the use of Operational Transformation - an area of ongoing research that has gained a lot of press lately thanks to Google Wave.

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 - Operational Transform