Picture: Aizkolariak (wood chopping) on the Trinitate Plaza in San Sebastián
The Hybrid Publishing Consortium, the publishing technology infrastructure project of the Hybrid Publishing Lab, looks into algorithms that underly digital publishing development, in a series of articles on our notepad blog. Starting with ‘Operational Transformation’ (OT) which underpins collaborative editing.
Collaborative editing is making slow, halted, but significant progress into the field of text editing. Most people will be familiar with Etherpad and GoogleDocs, some people might have heard of MS Office 365, and in the mist of Internet mythology, 2008, there is Google Wave. All of these pseudo-real-time editors are using the OT algorithm for collaborative editing. There is an in depth comparison of Google’s and Microsoft approaches to the new office products by TechRepublic. But what is obvious is that the move away from the isolated authoring of the desktop word processor or DTP tools is on the horizon. Both these main word processor providers, Google and Microsoft, are now cloud based, with MS Office moving to subscription purchase only as of 2013.
OT had its origins back in the 1980s with work on ‘software versioning systems’ as used by GitHub, with an algorithm called GROVE (GRoup Outline Viewing Edit).
With the short comings being addressed in the 1990s by the likes of Professor Sun Chengzheng, of Singapore University, developing the OT algorithm.
OT was designed for collaborative editing on networks, like the internet, with long time delay in communication, known as high latency. With a potential 64,000 km round trip for a document between to collaborators on the internet, the latency is at a minimum of 200ms. Where as a word processor user expects feedback times of under 100ms, so something has to give. It could be said that OT fudges, or fakes, real-time collaboration to achieve the appearance of real-time editing for the user. If multiple users are editing a document the potential variations quickly spirals out of control once you are above three users, making the computation problem very hard to solve.
OT’s trick, which is carried in it’s name ‘Transformation’, is to shuffle around in the background all the potential scenarios, or potential ‘Transformations’, and distribute them to the different users computers. For real-time collaborative editing, not every character typed needs to be distributed to all users simultaneously, hence this background shuffling of potential ‘Transformations’ can take place. But what needs to happen is consistency and convergence, hence this background shuffling will enable feedback to a user who goes to edit a line of text on their own screen that happens to have been deleted by another user earlier, but wasn’t updated in time to refresh the editors screen.
Operational Transformation Frequently Asked Questions and Answers