Thoughts and Stuff

photography and coding and running and bananas

Google Wave Whitepapers

Google Wave (sadly deprecated) has pioneered a lot of what drives modern-day Google Docs, Slides, etc. in terms of an OT framework – thankfully, the project has led to a series of whitepapers discussing the technologies present in Wave, and even more happily, the original source code was open-sourced.

Sources

  1. Google Wave whitepapers
  2. High-Latency, Low-Bandwidth Windowing in the Jupiter Collaboration System (Nichols 1995)

Implementing dOPT

09.25.2014 writeup Minke Zhang

Implementing Cormack’s 1995 paper was more straightforward than I anticipated; as per the previous discussion with the author, I went ahead and implemented the corrected dOPT algorithm for a tree topology. The source code at the time of this writing can be found on Github for reference; all tests are passing, and no known bugs exist. Any questions on the source code can be directed to me.

Continue reading

An Update on dOPT

In the process of implementing Cormack’s correction to the dOPT algorithm, I’ve come across several other papers which provide a more complete background of operational transforms and may be of use in the future. They are listed here for sake of documentation – a review of these papers will be provided once I read them carefully.

Resources

  1. A Calculus for Concurrent Update (Cormack 1995)
  2. Proof of Correctness of Ressel’s adOPTed Algorithm (Lushman and Cormack 2003)
  3. Transformation-Based Concurrency Control in Groupware Systems (Lushman 2002)

A Counterexample to dOPT (Cormack 1995)

09.10.2014 writeup Minke Zhang
Cormack’s 1995 paper shows a flaw in the original dOPT algorithm, in showing that the strength of the algorithm – the completely decentralized nature of the messaging protocol – leads to divergent states across different clients. Fortunately, Cormack outlines a possible way to fix the algorithm, provided that message passing between nodes is retricted to a point-to-point protocol – that is, we can no longer afford the luxury in a network topology of having circular circuits. Continue reading

Concurrency Control in Groupware Systems

What follows is an overview of a 1989 journal article by Ellis and Gibbs regarding collaborative editing. It is the origin of the use of operational transforms. For me, it is particularly useful as the dOPT algorithm for reconstructing a cohoerent global state is introduced here. The global state, in the case of the concurrent text editor, is the contents of the document. In more complex scenarios, the state can consist of much more ill-defined properties – in the case of Google Docs, the state would consist of not only the document text, but also the style rendered (bold, italic, etc. Continue reading