Aizkolariak (wood chopping) on the Trinitate Plaza in San SebastiánPicture: 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.

Issues and Experiences in Designing Real-time Collaborative Editing Systems. Professor Sun Chengzheng. Google Tech Talks, 2008.

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.

The Node.js the Javascript framework is also using OT in the form of Share.js. Share.js was written by a former Google Wave engineer and is Open Source and in the notes on the site shows how difficult the real-time collaborative editing problem has been, with Google Wave taking two years to build and the engineer saying it would take the same amount of time to rebuild. In a way Etherpad points to difficulties of developing OT. If you look at Etherpad’s text editing functionality, it does real-time well, but its a long way from being a word processors, about fifteen steps away, but these are steps that will get made, then word processing will become a whole new ball game. 

Operational Transformation Frequently Asked Questions and Answers



Simon Worthington

Posts Twitter

Street MBA, technologist, art freaker, dreampunk, organiser, media activist, publisher and book nut. Co-founder of Mute Magazine Skilled as an artist at Falmouth Art School, The Slade School of Fine Art, UCL, London and at CalArts, Valencia, California.

No Comments

Be the first to start the conversation.

Leave a Reply