Ray Valdes

A member of the Gartner Blog Network

Ray Valdes
Research VP
9 years at Gartner
30 years IT industry

Ray Valdes is research director in Gartner Research, where he is part of the Internet Platforms and Web Services team. Read Full Bio

Coverage Areas:

The Secret Sauce Behind Google Wave

by Ray Valdes  |  May 31, 2009  |  17 Comments

Apologies for the provocative headline, but I just couldn’t resist. Actually, there is no single secret sauce, but rather multiple key ingredients of varying degrees of obscurity.

Google Wave is a fascinating melange of audacity and hope. Google has blended multiple, powerful, sauces into this melange, some secret and other less so. One in particular that was quite obscure to me is operational transformation (OT) theory, which is the algorithmic framework that enables multiple people to edit a single document in real-time across a wide-area network with unpredictable latency. More about this in a moment.

As I stated in last week’s blog entry, written minutes after the keynote ended at the Google I/O conference, Wave has surprisingly broad scope, cutting across formerly separate application categories like email, blogging, wikis and instant messaging. My initial reaction was colored by instinctive reflex of cynicism, and basically amounted to: Yes, it’s very cool and innovative, but what has Google done for the enterprise lately?

After a healthy debate with Gartner colleagues, spanning a range of views pro and con, I reviewed the Wave video and the documentation, and felt greater excitement than I did during the keynote (where I was one of the few sitting down during the standing ovation). I won’t use this post to make one of those forecasts, such as “Google Wave will kill X”, where X can be any number of well-known vendors or products. That kind of statement is overly glib, because we are just a few days into a scenario that will take 5 years or more to play out, with many twists and turns along the way.

Instead, I want to first draw your attention to some of the enabling technologies that represent the key ingredients behind Wave, and then talk about OT.

Key enabling technologies include:

  • GWT Ajax library, which not only powers complex interactions on a browser, but also provides a reasonably tuned rendering for small form-factor mobile devices, such as Android and iPhone
  • XMPP protocol that provides a foundation for the Wave Federation Protocol
  • the real-time keystroke-by-keystroke communication pioneered several years ago in Google Suggest, and now in production in high-scalability deployment
  • the AppEngine cloud computing platform on which are hosted the Robot extensions to Wave
  • the Big Table data persistence mechanism that powers Google’s implementation of a Wave server (something which is not required by the spec, but which facilitates developer productivity and production scalability)

Note that these are only enabling technologies, and Wave is a large collection of software built using these enabling technologies by a hundred-person team over the past two years. That system is currently in closed beta, so the best we can do is circle around it and measure where we can.

All of the above items have been discussed over the past months or years in the industry circles, so none of these qualifies as a “secret sauce”. Imho, if there is a secret sauce, it is Google’s extensions to operational transformation theory (OT).

OT is an area of computer science that spans decades, but is nevertheless obscure. The name is derived from the on-the-fly transformation of operations (in the case of a word processing document, the operations would be things like inserting or deleting text) to enable multiple independent reads and writes without locking. One phrase comes up again and again in the literature, is that this is an “optimistic” approach — not in the everyday sense of audacity and hope, but in a technical sense where each parallel repository of content takes its own path to an eventually consistent state.

So this Saturday evening, instead of going out to the movies, I decided to entertain my curiosity by looking further into OT. Here are some tidbits I found while scanning an area that is new to me. It is possible I have missed major landmarks and garbled some of the concepts in this rich and fascinating area. Like a tourist in an unfamiliar realm, I am enjoying the sights even though their significance might not be fully apparent.

Here is a simple illustrative sketch of OP, from well-known researcher Dr Chengzhen Sun, that hopefully will become more clear by the end of this blog post:


Operational Transformation in Real-Time Editing

Seminal work that preceded OT was done by Leslie Lamport, one of the giants in computer science, in 1978 in a classic paper called “Time, Clocks and the Ordering of Events in a Distributed System”. This paper presented a fundamental algorithm for distributed computing based on distributed state machines, time stamps, and vector clocks. Lamport later said that his algorithm was based on his understanding of Special Relativity, which “teaches us that there is no invariant total ordering of events in space-time; different observers can disagree about which of two events happened first. There is only a partial order in which an event e1 precedes an event e2 iff e1 can causally affect e2.

In an interesting side note, Lamport works for Microsoft Research these days.

Here is a simplified version of Lamport’s algorithm for distributed mutual exclusion, from a paper by RR Hoogerwoord in 2002.

Lamport’s work is generally applicable across many aspects of computer science, but is referenced by researchers in the field known as group editing. A pioneering work in collaborative authoring systems was by C.A. Ellis and S.E. Gibbs in 1989 on “Concurrency Control in Groupware Systems”. . There is a whole community of researchers that have been working in this field, but Dr. Clarence Ellis is one of pioneers. In an interesting side note, Ellis was the first African-American to get a PhD in Computer Science in 1969 (see his photo from that era).

Later on, in 1998, there was an important paper by Chengzheng Sun and Clarence Ellis on “Operational transformation in real-time group editors” This paper was followed by further work by Chengzheng Sun at Griffith University in Australia. (Is it a coincidence that the Google Wave team is based there?).

One of Dr Sun’s projects is CoWord, an attempt to retrofit Microsoft Word with real-time collaborative editing features (like those demonstrated by Google): CoWord seeks

“to apply the state-of-the-art collaborative editing technologies to widely used single-user commercial word processors in a transparent way, i.e., without modifying the source code of single-user applications. MS Word has been chosen as the first target of this application. A collaborative Word (named as CoWord) is being built in our lab, which not only retains existing MS Word features, but also includes new features that enable multiple users to perform and undo MS Word editing operations on the same MS Word document concurrently and consistently.”

Interestingly, Sun presented his work in a lecture to Microsoft Research in 2003. (Also worth noting is that Sun recently moved to Nanyang Technological University at Singapore.)

The above are only a couple of representative pieces in a swath of research in this field. My understanding is that Google has built on this work and come up with their own innovations, which I know about only as a distant observer. One of those innovations, I understand, has to do with maintaining a representation of a Wave as a tree structure in the browser, and keeping this structure in synch with the server version and that on other machines. If that is the case, I ran across a patent issued in 2005 that seems to be directly relevant: “Browser to browser, DOM-based, peer-to-peer communication with delta synchronization”:

“The present invention solves the complexity of integration of Web browsing, Web authoring and Instant Messaging, and offers the uniqueness of browser-based rich media manipulation and synchronization of Web contents among participating peers. The advantages are exemplified in the combination of the three…”

I’ll stop here to let the patent lawyers fire up their engines.

One last, possibly unrelated landmark, in my Saturday night tour of OT, is a variant approach which seeks the same goal as OT, to maintain consistency of shared data as it is manipulated by distributed authors in real time. The authors have come up with an approach that does not have to use vector clocks and is supposedly simpler and more efficient than classic OT. Because this approach is “With Out Operational Transform“, the authors chose the charming name of WOOT.

Updated (6/5/09): Corrected a typo (pointed out by Shantanu in comments).

17 Comments »

Category: Uncategorized     Tags:

17 responses so far ↓

  • 1 Yefim Natis   May 31, 2009 at 10:42 am

    exciting. like a travel report. Thanks, Ray.

    I wonder if Google Docs that also have a shared simultaneous document processing (although not at a keystroke granularity) is a pre-cursor to the more advanced form of it in Wave.

    More generally, I think that the danger for Google is to create a service that is too big, too complex for an ordinary user. You will know if they are avoiding this danger if it turns out that sending a simple e-mail, a simple IM message or making a simple blog post in Wave is just as simple and straight-forward as it was. The complexity should not show until you ask for it (as in iGoogle vs. Google). In the end, to begin to replace the now-classic alternatives, this collaboration as a service (CaaS) tool must work well both for shared and for individual activities.

  • 2 Ray Valdes   May 31, 2009 at 3:49 pm

    Yefim, yes you are right: the near-real-time collaboration in Google Docs is a precursor.

    Also, there are some other word processors that go beyond Docs toward a Wave-like experience. For example, Virtual Ubiquity was an eleven-person startup that did the Buzzword online document editing, which is built with Adobe Flash technology. The company was acquired not long ago by Adobe (see http://www.adobe.com/acom/buzzword/).

    You make an important point about the risk of losing simplicity as features proliferate. That is a challenge that other long-established products have had to struggle with, from Microsoft Word to Lotus Notes. It will be interesting to see how Wave handles this challenge.

  • 3 Google Wants to Make Wave. Joe Wants to Create a PC Game. Discuss.   May 31, 2009 at 8:18 pm

    [...] things like that. Google Wave is a medium, and one which will (apparently) support a key standard. This is, in short, the potential start of a very big deal. Or, it could crater, and in three years we could be reading interviews with Google folks talking [...]

  • 4 Shantanu   June 1, 2009 at 5:00 am

    Thought provoking for me. The underline is “Realtime collaboration”. There are a lot of applications waiting to leverage the concept.
    One possible correction. Did you mean “African-American”?

  • 5 Ludovic Dubost   June 1, 2009 at 7:47 am

    Very nice that you have picked-up the WOOT algorithm. WOOT is being used by XWiki Concerto (http://concerto.xwiki.org) a common work by XWiki, INRIA, Mandriva, Telecom Paris to make a P2P replicable wiki. “XWoot” is a module able to connect to a plain XWiki Engine and replicate all it’s content with other running servers.

    It’s very nice to see Google working on this and doing it as open-source. What is really improssive is if they have done a full browser level implementation of OT. This will really open great possibilities.

  • 6 Ludovic Dubost   June 1, 2009 at 8:31 am

    Small addition: XWiki Concerto uses WOOTO an optimized version of WOOT (described in this PDF http://wooki.sourceforge.net/papers/RR-6226-2.pdf)

    If there are people interested in this, we (XWiki) are on the OW2 booth at JavaOne this week.

  • 7 Ray Valdes   June 1, 2009 at 4:31 pm

    Shantanu, thanks for your comment (and for the correction!)

    Ludovic, thanks for the info. I will seek out XWiki at JavaOne this week.

  • 8 Knowtu » links for 2009-06-01   June 1, 2009 at 9:04 pm

    [...] The Secret Sauce Behind Google Wave – operational transformation theory (tags: google algorithms) [...]

  • 9 Brian K Seitz   June 2, 2009 at 7:20 pm

    The interesting thing is the ability to track, replay and edit structures in a graphical UI. Within the Product Structure domain, STEP Tools, a small company working in Product Definition Data had created a similar set of function, but without the graphical UI.

    The ability to manage structure whether temporial or other relationships is a very powerful capability, one that has yet to be exploited very well. hether Google can captialize on this advancement remains to be seen.

  • 10 David S.   June 3, 2009 at 3:52 pm

    Hey Ray. As a researcher working on OT, I’m very intrigued by the tech community’s taking a keen interest in this technology after the Wave splash. You may find interesting this recent Google Tech talk on CoWord and OT at http://www.youtube.com/watch?v=84zqbXUQIHc. It gives a concise and tangible introduction to the technology and demos its usage in the most recent version of CoWord.

  • 11 Espace de François » Blog Archive » Google Wave en quelques mots   June 3, 2009 at 6:59 pm

    [...] A titre d’illustration, le fameux cabinet Gartner y a déjà consacré deux posts dont un sur les bases algorithmiques de Google Wave (notamment l’OT, ou Operational Transformation, la théorie à la base de la gestion des [...]

  • 12 David S.   June 4, 2009 at 1:25 am

    A minor correction: the URL for the our CoWord Online Demo can found here:
    http://cooffice.ntu.edu.sg/coword/.

    For those interested, the CoWord Microsoft Research talk can be found here:
    http://cooffice.ntu.edu.sg/coword/vods/lecture.htm

  • 13 Analysts are cynics – a dead idea « SageCircle Blog   June 5, 2009 at 9:06 am

    [...] Back Story: It is common for many vendor executives to think of industry analysts as cynical. And at first glance, Gartner analyst Ray Valdez (bio, blog, Twitter) would seem to confirm this perception by characterizing his reaction to a vendor’s announcement as cynicism in his blog post The Secret Sauce Behind Google Wave.  [...]

  • 14 Ray Valdes   June 5, 2009 at 12:14 pm

    David S, thanks for the info.

    All: I have updated this post to correct the small but important typo pointed out by Shantanu earlier (“American-American” –> “African-American”). Also changed the size of the first image slightly for better visibility.

  • 15 More details about Google Wave « Cjed Audio blog   June 6, 2009 at 6:49 pm

    [...] key foundation technologies to Google Wave are (see also details in original article The Secret Sauce Behind Google Wave) : – GWT Ajax library, which not only powers complex interactions on a browser, but also provides a [...]

  • 16 Google Chrome, Microsoft Gazelle and the cloud-oriented OS   July 8, 2009 at 6:45 am

    [...] ← The Secret Sauce Behind Google Wave [...]

  • 17 Eldon Schneider   January 14, 2010 at 3:20 pm

    Oooh interesting research you got there. Now google wave is really making a giant splash in the internet. Amazing. Thanks for sharing.