whitepapers/operational-transform/operational-transform.html - incubator-retired-wave - Git at Google

 <?xml version="1.0" encoding="utf-8" ?>
 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
 <head>
 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
 <meta name="generator" content="Docutils 0.4.1: http://docutils.sourceforge.net/" />
 <title>Google Wave Operational Transformation</title>
 <meta name="authors" content="David Wang  Alex Mah  Soren Lassen" />
 <style type="text/css">

 /*
 :Author: David Goodger
 :Contact: goodger@users.sourceforge.net
 :Date: $Date: 2005-12-18 01:56:14 +0100 (Sun, 18 Dec 2005) $
 :Revision: $Revision: 4224 $
 :Copyright: This stylesheet has been placed in the public domain.

 Default cascading style sheet for the HTML output of Docutils.

 See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
 customize this style sheet.
 */

 /* used to remove borders from tables and images */
 .borderless, table.borderless td, table.borderless th {
   border: 0 }

 table.borderless td, table.borderless th {
   /* Override padding for "table.docutils td" with "! important".
      The right padding separates the table cells. */
   padding: 0 0.5em 0 0 ! important }

 .first {
   /* Override more specific margin styles with "! important". */
   margin-top: 0 ! important }

 .last, .with-subtitle {
   margin-bottom: 0 ! important }

 .hidden {
   display: none }

 a.toc-backref {
   text-decoration: none ;
   color: black }

 blockquote.epigraph {
   margin: 2em 5em ; }

 dl.docutils dd {
   margin-bottom: 0.5em }

 /* Uncomment (and remove this text!) to get bold-faced definition list terms
 dl.docutils dt {
   font-weight: bold }
 */

 div.abstract {
   margin: 2em 5em }

 div.abstract p.topic-title {
   font-weight: bold ;
   text-align: center }

 div.admonition, div.attention, div.caution, div.danger, div.error,
 div.hint, div.important, div.note, div.tip, div.warning {
   margin: 2em ;
   border: medium outset ;
   padding: 1em }

 div.admonition p.admonition-title, div.hint p.admonition-title,
 div.important p.admonition-title, div.note p.admonition-title,
 div.tip p.admonition-title {
   font-weight: bold ;
   font-family: sans-serif }

 div.attention p.admonition-title, div.caution p.admonition-title,
 div.danger p.admonition-title, div.error p.admonition-title,
 div.warning p.admonition-title {
   color: red ;
   font-weight: bold ;
   font-family: sans-serif }

 /* Uncomment (and remove this text!) to get reduced vertical space in
    compound paragraphs.
 div.compound .compound-first, div.compound .compound-middle {
   margin-bottom: 0.5em }

 div.compound .compound-last, div.compound .compound-middle {
   margin-top: 0.5em }
 */

 div.dedication {
   margin: 2em 5em ;
   text-align: center ;
   font-style: italic }

 div.dedication p.topic-title {
   font-weight: bold ;
   font-style: normal }

 div.figure {
   margin-left: 2em ;
   margin-right: 2em }

 div.footer, div.header {
   clear: both;
   font-size: smaller }

 div.line-block {
   display: block ;
   margin-top: 1em ;
   margin-bottom: 1em }

 div.line-block div.line-block {
   margin-top: 0 ;
   margin-bottom: 0 ;
   margin-left: 1.5em }

 div.sidebar {
   margin-left: 1em ;
   border: medium outset ;
   padding: 1em ;
   background-color: #ffffee ;
   width: 40% ;
   float: right ;
   clear: right }

 div.sidebar p.rubric {
   font-family: sans-serif ;
   font-size: medium }

 div.system-messages {
   margin: 5em }

 div.system-messages h1 {
   color: red }

 div.system-message {
   border: medium outset ;
   padding: 1em }

 div.system-message p.system-message-title {
   color: red ;
   font-weight: bold }

 div.topic {
   margin: 2em }

 h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
 h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
   margin-top: 0.4em }

 h1.title {
   text-align: center }

 h2.subtitle {
   text-align: center }

 hr.docutils {
   width: 75% }

 img.align-left {
   clear: left }

 img.align-right {
   clear: right }

 ol.simple, ul.simple {
   margin-bottom: 1em }

 ol.arabic {
   list-style: decimal }

 ol.loweralpha {
   list-style: lower-alpha }

 ol.upperalpha {
   list-style: upper-alpha }

 ol.lowerroman {
   list-style: lower-roman }

 ol.upperroman {
   list-style: upper-roman }

 p.attribution {
   text-align: right ;
   margin-left: 50% }

 p.caption {
   font-style: italic }

 p.credits {
   font-style: italic ;
   font-size: smaller }

 p.label {
   white-space: nowrap }

 p.rubric {
   font-weight: bold ;
   font-size: larger ;
   color: maroon ;
   text-align: center }

 p.sidebar-title {
   font-family: sans-serif ;
   font-weight: bold ;
   font-size: larger }

 p.sidebar-subtitle {
   font-family: sans-serif ;
   font-weight: bold }

 p.topic-title {
   font-weight: bold }

 pre.address {
   margin-bottom: 0 ;
   margin-top: 0 ;
   font-family: serif ;
   font-size: 100% }

 pre.literal-block, pre.doctest-block {
   margin-left: 2em ;
   margin-right: 2em ;
   background-color: #eeeeee }

 span.classifier {
   font-family: sans-serif ;
   font-style: oblique }

 span.classifier-delimiter {
   font-family: sans-serif ;
   font-weight: bold }

 span.interpreted {
   font-family: sans-serif }

 span.option {
   white-space: nowrap }

 span.pre {
   white-space: pre }

 span.problematic {
   color: red }

 span.section-subtitle {
   /* font-size relative to parent (h1..h6 element) */
   font-size: 80% }

 table.citation {
   border-left: solid 1px gray;
   margin-left: 1px }

 table.docinfo {
   margin: 2em 4em }

 table.docutils {
   margin-top: 0.5em ;
   margin-bottom: 0.5em }

 table.footnote {
   border-left: solid 1px black;
   margin-left: 1px }

 table.docutils td, table.docutils th,
 table.docinfo td, table.docinfo th {
   padding-left: 0.5em ;
   padding-right: 0.5em ;
   vertical-align: top }

 table.docutils th.field-name, table.docinfo th.docinfo-name {
   font-weight: bold ;
   text-align: left ;
   white-space: nowrap ;
   padding-left: 0 }

 h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
 h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
   font-size: 100% }

 tt.docutils {
   background-color: #eeeeee }

 ul.auto-toc {
   list-style-type: none }

 </style>
 </head>
 <body>
 <div class="document" id="google-wave-operational-transformation">
 <h1 class="title">Google Wave Operational Transformation</h1>
 <table class="docinfo" frame="void" rules="none">
 <col class="docinfo-name" />
 <col class="docinfo-content" />
 <tbody valign="top">
 <tr><th class="docinfo-name">Authors:</th>
 <td>David Wang
 <br />Alex Mah
 <br />Soren Lassen</td></tr>
 <tr><th class="docinfo-name">Version:</th>
 <td>1.1 - July 2010</td></tr>
 </tbody>
 </table>
 <p>This whitepaper is part of a series. All of the whitepapers
 can be found on <a class="reference" href="http://www.waveprotocol.org/whitepapers">Google Wave Federation Protocol site</a>.</p>
 <p>Waves are hosted, structured documents that allow seamless and low latency concurrent
 modifications.  To provide this live experience, Google Wave uses the Operational
 Transformation (OT) framework of concurrency control.</p>
 <div class="section">
 <h1><a id="executive-summary" name="executive-summary">Executive Summary</a></h1>
 <p>Collaborative document editing means multiple editors are able to edit a
 shared document at the same time. It is live and concurrent when a user can see
 the changes another person is making, keystroke by keystroke.
 Google Wave offers live concurrent editing of rich text documents.</p>
 <p>The result is that Google Wave allows for a very engaging conversation where you can
 see what the other person is typing, character by character, much like how you
 would converse in a cafe. This is very much like instant messaging except you
 can see what the other person is typing, live. Google Wave also allows for a more
 productive collaborative document editing experience, where people don't have
 to worry about stepping on each others toes and still use common word processor
 functionalities such as bold, italics, bullet points, and headings.</p>
 <p>Waves are more than just rich text documents. In fact, Google Wave's core technology
 allows live concurrent modifications of structured documents which can be used to
 represent any structured content including system data that is shared between
 clients and backend systems.</p>
 <p>To achieve these goals, Google Wave uses a concurrency control system based on
 Operational Transformation.</p>
 </div>
 <div class="section">
 <h1><a id="introduction" name="introduction">Introduction</a></h1>
 <p>Operational transformation (OT) is a theoretical framework of concurrency
 control that has been continuously researched in the context of group editing
 for more than 10 years. This document does not describe the basic theory of OT
 and assumes the reader understands OT. The reader is encouraged to read the
 documents in the reference section for background.</p>
 <p>In short, Wave OT replicates the shared document at all sites and allows any
 user to edit any part of the document at any time. Local editing operations are
 executed without being delayed or blocked. Remote operations are transformed
 before execution. The lock-free, non-blocking property of OT makes the local
 response time insensitive to networking latencies. These properties of OT play
 a big part in providing the Optimistic User Interface (UI) of Wave. Optimistic
 UI means user actions are executed and displayed locally to the user
 immediately without waiting for the server to respond.</p>
 <p>The starting point for Wave OT was the paper &quot;High-latency, low-bandwidth
 windowing in the Jupiter collaboration system&quot;. Like the Jupiter system
 described by the paper, Google Wave also implements a client and server based OT
 system. The reader is again encouraged to read this paper for background.</p>
 <p>This document describes the extensions Google Wave made to the basic theory of OT.</p>
 </div>
 <div class="section">
 <h1><a id="wave-extensions-to-operational-transformation" name="wave-extensions-to-operational-transformation">Wave Extensions to Operational Transformation</a></h1>
 <p>A wave is a collection of wavelets. A wavelet contains a collection of documents.
 A document consists of a structured, XML-like document and some annotations.
 A wavelet is where concurrent modification takes place.
 A wavelet is the object on which OT is applied.</p>
 <div class="section">
 <h2><a id="clients-wait-for-acknowledgement-from-server-before-sending-more-operations" name="clients-wait-for-acknowledgement-from-server-before-sending-more-operations">Clients wait for acknowledgement from server before sending more operations</a></h2>
 <p>To recap, under the basic theory of OT, a client can send operations
 sequentially to the server as quickly as it can. The server can do the same.
 This means the client and server can traverse through the state space via
 different OT paths to the same convergent state, depending on when they receive
 the other parties' operations. See diagram below.</p>
 <img alt="img/ot-paths.png" src="img/ot-paths.png" />
 <p>When you have multiple clients connected to the server, every client and server
 pair have their own state space. One shortcoming of this is the server needs
 to carry a state space for every connected client, which can be
 memory-intensive. In addition, this complicates the server algorithm by
 requiring it to convert clients' operations between state spaces.</p>
 <p>Having a simple and efficient server is important in making waves reliable and
 scalable. With this goal, Wave OT modifies the basic theory of OT by requiring
 the client to wait for acknowledgement from the server before sending more
 operations. When a server acknowledges a client's operation, it means the
 server has transformed the client's operation, applied it to the server's copy
 of the wavelet and broadcast the transformed operation to all other connected
 clients. Whilst the client is waiting for the acknowledgement, it caches
 operations produced locally and sends them in bulk later.</p>
 <p>With the addition of acknowledgements, a client can infer the server's OT path.
 We call this the inferred server path. By having this, the client can send
 operations to the server that are always on the server's OT path.</p>
 <p>This has the important benefit that the server only needs to have a single
 state space, which is the history of operations it has applied. When it
 receives a client's operation, it only needs to transform the operation against
 the operation history, apply the transformed operation, and then broadcast it.</p>
 <img alt="img/david_ot3.png" src="img/david_ot3.png" />
 <p>One trade-off of this simplification is that a client will see chunks of operations
 from another client in intervals of approximately one round trip time to the
 other client. We believe the server-side benefits make this a worthwhile trade-off.</p>
 </div>
 </div>
 <div class="section">
 <h1><a id="wavelet-operations" name="wavelet-operations">Wavelet Operations</a></h1>
 <p>Wavelet operations consist of document operations, for modifying documents,
 and non-document operations, for tasks such
 as adding or removing a wavelet participant. We'll focus on document
 operations here.</p>
 <div class="section">
 <h2><a id="document-support" name="document-support">Document Support</a></h2>
 <p>A document operation has a streaming interface, similar to an
 XMLStreamWriter or a SAX handler. The document operation consists of a sequence
 of ordered document mutations. The mutations are applied in sequence as you
 traverse the document linearly.</p>
 <p>Designing document operations in this manner makes it easier to write the
 transformation function and composition function described later.</p>
 <p>A wave document can be regarded as a single
 document operation that can be applied to the empty document.</p>
 <p>In Google Wave, every character, start tag or end tag in a document is called an item. Gaps
 between items are called positions. Position 0 is before the first item. A
 document operation can contain mutations that reference positions. For example,
 a &quot;Retain&quot; mutation specifies how many positions to skip ahead in the
 document before applying the next mutation.</p>
 <img alt="img/doc-items.png" src="img/doc-items.png" />
 <p>Wave document operations also support annotations. An annotation is some
 meta-data associated with an item range, i.e., a start position and an end
 position. This is particularly useful for describing text formatting and
 spelling suggestions, as it does not unecessarily complicate the underlying structured
 document format.</p>
 <img alt="img/annotations.png" src="img/annotations.png" />
 <p>Wave document operations consist of the following mutation components:</p>
 <ul class="simple">
 <li>retain</li>
 <li>insert characters</li>
 <li>insert element start</li>
 <li>insert element end</li>
 <li>delete characters</li>
 <li>delete element start</li>
 <li>delete element end</li>
 <li>replace attributes</li>
 <li>update attributes</li>
 <li>annotation boundary</li>
 </ul>
 <p>The following is a more complex example document operation.:</p>
 <pre class="literal-block">
 retain 3
 insert element start with tag &quot;p&quot; and no attributes
 insert characters &quot;Hi there!&quot;
 insert element end
 retain 5
 delete characters 4
 retain 2
 </pre>
 <p>From this, one can see how an entire document can be represented as a
 single document operation.</p>
 </div>
 <div class="section">
 <h2><a id="transformation-function" name="transformation-function">Transformation Function</a></h2>
 <p>Representing document operations using a stream interface has the benefit that
 it makes processing operations in a linear fashion easy.</p>
 <img alt="img/transformation.png" src="img/transformation.png" />
 <p>The operation transformer works by taking two streaming operations as input,
 simultaneously processing the two operations in a linear fashion, and
 outputting two streaming operations. This stream-style processing ensures that
 transforming a pair of very large operations is efficient.</p>
 </div>
 <div class="section">
 <h2><a id="composition" name="composition">Composition</a></h2>
 <p>The document operations have been engineered so that they can be composed
 together and the composition of any two document operations that can be
 composed together is itself a single document operation.</p>
 <p>Furthermore, the composition algorithm processes operations as linear streams,
 so the composition algorithm is efficient.</p>
 <img alt="img/composition.png" src="img/composition.png" />
 <p>The composition B∙A has the property that (B∙A)(d) = B(A(d))
 for all documents d on which A can be applied.</p>
 <p>While a Wave client awaits server acknowledgement, it composes all its
 pending operations. This reduces the number of operations to transform
 and send.</p>
 </div>
 </div>
 <div class="section">
 <h1><a id="references" name="references">References</a></h1>
 <p>&quot;Operational transformation&quot;. In Wikipedia, the free encyclopedia, May 28, 2009. <a class="reference" href="http://en.wikipedia.org/wiki/Operational_transformation">http://en.wikipedia.org/wiki/Operational_transformation</a></p>
 <p>David A. Nichols, Pavel Curtis, Michael Dixon, and John Lamping: <a class="reference" href="http://doi.acm.org/10.1145/215585.215706">High-latency, low-bandwidth windowing in the Jupiter collaboration system</a>, UIST '95: Proceedings of the 8th annual ACM symposium on User interface and software technology, pp.111-120. ACM, 1995.</p>
 </div>
 </div>
 </body>
 </html>
	<?xml version="1.0" encoding="utf-8" ?>
	<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
	<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
	<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
	<meta name="generator" content="Docutils 0.4.1: http://docutils.sourceforge.net/" />
	<title>Google Wave Operational Transformation</title>
	<meta name="authors" content="David Wang Alex Mah Soren Lassen" />
	<style type="text/css">

	/*
	:Author: David Goodger
	:Contact: goodger@users.sourceforge.net
	:Date: $Date: 2005-12-18 01:56:14 +0100 (Sun, 18 Dec 2005) $
	:Revision: $Revision: 4224 $
	:Copyright: This stylesheet has been placed in the public domain.

	Default cascading style sheet for the HTML output of Docutils.

	See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
	customize this style sheet.
	*/

	/* used to remove borders from tables and images */
	.borderless, table.borderless td, table.borderless th {
	border: 0 }

	table.borderless td, table.borderless th {
	/* Override padding for "table.docutils td" with "! important".
	The right padding separates the table cells. */
	padding: 0 0.5em 0 0 ! important }

	.first {
	/* Override more specific margin styles with "! important". */
	margin-top: 0 ! important }

	.last, .with-subtitle {
	margin-bottom: 0 ! important }

	.hidden {
	display: none }

	a.toc-backref {
	text-decoration: none ;
	color: black }

	blockquote.epigraph {
	margin: 2em 5em ; }

	dl.docutils dd {
	margin-bottom: 0.5em }

	/* Uncomment (and remove this text!) to get bold-faced definition list terms
	dl.docutils dt {
	font-weight: bold }
	*/

	div.abstract {
	margin: 2em 5em }

	div.abstract p.topic-title {
	font-weight: bold ;
	text-align: center }

	div.admonition, div.attention, div.caution, div.danger, div.error,
	div.hint, div.important, div.note, div.tip, div.warning {
	margin: 2em ;
	border: medium outset ;
	padding: 1em }

	div.admonition p.admonition-title, div.hint p.admonition-title,
	div.important p.admonition-title, div.note p.admonition-title,
	div.tip p.admonition-title {
	font-weight: bold ;
	font-family: sans-serif }

	div.attention p.admonition-title, div.caution p.admonition-title,
	div.danger p.admonition-title, div.error p.admonition-title,
	div.warning p.admonition-title {
	color: red ;
	font-weight: bold ;
	font-family: sans-serif }

	/* Uncomment (and remove this text!) to get reduced vertical space in
	compound paragraphs.
	div.compound .compound-first, div.compound .compound-middle {
	margin-bottom: 0.5em }

	div.compound .compound-last, div.compound .compound-middle {
	margin-top: 0.5em }
	*/

	div.dedication {
	margin: 2em 5em ;
	text-align: center ;
	font-style: italic }

	div.dedication p.topic-title {
	font-weight: bold ;
	font-style: normal }

	div.figure {
	margin-left: 2em ;
	margin-right: 2em }

	div.footer, div.header {
	clear: both;
	font-size: smaller }

	div.line-block {
	display: block ;
	margin-top: 1em ;
	margin-bottom: 1em }

	div.line-block div.line-block {
	margin-top: 0 ;
	margin-bottom: 0 ;
	margin-left: 1.5em }

	div.sidebar {
	margin-left: 1em ;
	border: medium outset ;
	padding: 1em ;
	background-color: #ffffee ;
	width: 40% ;
	float: right ;
	clear: right }

	div.sidebar p.rubric {
	font-family: sans-serif ;
	font-size: medium }

	div.system-messages {
	margin: 5em }

	div.system-messages h1 {
	color: red }

	div.system-message {
	border: medium outset ;
	padding: 1em }

	div.system-message p.system-message-title {
	color: red ;
	font-weight: bold }

	div.topic {
	margin: 2em }

	h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
	h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
	margin-top: 0.4em }

	h1.title {
	text-align: center }

	h2.subtitle {
	text-align: center }

	hr.docutils {
	width: 75% }

	img.align-left {
	clear: left }

	img.align-right {
	clear: right }

	ol.simple, ul.simple {
	margin-bottom: 1em }

	ol.arabic {
	list-style: decimal }

	ol.loweralpha {
	list-style: lower-alpha }

	ol.upperalpha {
	list-style: upper-alpha }

	ol.lowerroman {
	list-style: lower-roman }

	ol.upperroman {
	list-style: upper-roman }

	p.attribution {
	text-align: right ;
	margin-left: 50% }

	p.caption {
	font-style: italic }

	p.credits {
	font-style: italic ;
	font-size: smaller }

	p.label {
	white-space: nowrap }

	p.rubric {
	font-weight: bold ;
	font-size: larger ;
	color: maroon ;
	text-align: center }

	p.sidebar-title {
	font-family: sans-serif ;
	font-weight: bold ;
	font-size: larger }

	p.sidebar-subtitle {
	font-family: sans-serif ;
	font-weight: bold }

	p.topic-title {
	font-weight: bold }

	pre.address {
	margin-bottom: 0 ;
	margin-top: 0 ;
	font-family: serif ;
	font-size: 100% }

	pre.literal-block, pre.doctest-block {
	margin-left: 2em ;
	margin-right: 2em ;
	background-color: #eeeeee }

	span.classifier {
	font-family: sans-serif ;
	font-style: oblique }

	span.classifier-delimiter {
	font-family: sans-serif ;
	font-weight: bold }

	span.interpreted {
	font-family: sans-serif }

	span.option {
	white-space: nowrap }

	span.pre {
	white-space: pre }

	span.problematic {
	color: red }

	span.section-subtitle {
	/* font-size relative to parent (h1..h6 element) */
	font-size: 80% }

	table.citation {
	border-left: solid 1px gray;
	margin-left: 1px }

	table.docinfo {
	margin: 2em 4em }

	table.docutils {
	margin-top: 0.5em ;
	margin-bottom: 0.5em }

	table.footnote {
	border-left: solid 1px black;
	margin-left: 1px }

	table.docutils td, table.docutils th,
	table.docinfo td, table.docinfo th {
	padding-left: 0.5em ;
	padding-right: 0.5em ;
	vertical-align: top }

	table.docutils th.field-name, table.docinfo th.docinfo-name {
	font-weight: bold ;
	text-align: left ;
	white-space: nowrap ;
	padding-left: 0 }

	h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
	h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
	font-size: 100% }

	tt.docutils {
	background-color: #eeeeee }

	ul.auto-toc {
	list-style-type: none }

	</style>
	</head>
	<body>
	<div class="document" id="google-wave-operational-transformation">
	<h1 class="title">Google Wave Operational Transformation</h1>
	<table class="docinfo" frame="void" rules="none">
	<col class="docinfo-name" />
	<col class="docinfo-content" />
	<tbody valign="top">
	<tr><th class="docinfo-name">Authors:</th>
	<td>David Wang
	<br />Alex Mah
	<br />Soren Lassen</td></tr>
	<tr><th class="docinfo-name">Version:</th>
	<td>1.1 - July 2010</td></tr>
	</tbody>
	</table>
	<p>This whitepaper is part of a series. All of the whitepapers
	can be found on <a class="reference" href="http://www.waveprotocol.org/whitepapers">Google Wave Federation Protocol site</a>.</p>
	<p>Waves are hosted, structured documents that allow seamless and low latency concurrent
	modifications. To provide this live experience, Google Wave uses the Operational
	Transformation (OT) framework of concurrency control.</p>
	<div class="section">
	<h1><a id="executive-summary" name="executive-summary">Executive Summary</a></h1>
	<p>Collaborative document editing means multiple editors are able to edit a
	shared document at the same time. It is live and concurrent when a user can see
	the changes another person is making, keystroke by keystroke.
	Google Wave offers live concurrent editing of rich text documents.</p>
	<p>The result is that Google Wave allows for a very engaging conversation where you can
	see what the other person is typing, character by character, much like how you
	would converse in a cafe. This is very much like instant messaging except you
	can see what the other person is typing, live. Google Wave also allows for a more
	productive collaborative document editing experience, where people don't have
	to worry about stepping on each others toes and still use common word processor
	functionalities such as bold, italics, bullet points, and headings.</p>
	<p>Waves are more than just rich text documents. In fact, Google Wave's core technology
	allows live concurrent modifications of structured documents which can be used to
	represent any structured content including system data that is shared between
	clients and backend systems.</p>
	<p>To achieve these goals, Google Wave uses a concurrency control system based on
	Operational Transformation.</p>
	</div>
	<div class="section">
	<h1><a id="introduction" name="introduction">Introduction</a></h1>
	<p>Operational transformation (OT) is a theoretical framework of concurrency
	control that has been continuously researched in the context of group editing
	for more than 10 years. This document does not describe the basic theory of OT
	and assumes the reader understands OT. The reader is encouraged to read the
	documents in the reference section for background.</p>
	<p>In short, Wave OT replicates the shared document at all sites and allows any
	user to edit any part of the document at any time. Local editing operations are
	executed without being delayed or blocked. Remote operations are transformed
	before execution. The lock-free, non-blocking property of OT makes the local
	response time insensitive to networking latencies. These properties of OT play
	a big part in providing the Optimistic User Interface (UI) of Wave. Optimistic
	UI means user actions are executed and displayed locally to the user
	immediately without waiting for the server to respond.</p>
	<p>The starting point for Wave OT was the paper "High-latency, low-bandwidth
	windowing in the Jupiter collaboration system". Like the Jupiter system
	described by the paper, Google Wave also implements a client and server based OT
	system. The reader is again encouraged to read this paper for background.</p>
	<p>This document describes the extensions Google Wave made to the basic theory of OT.</p>
	</div>
	<div class="section">
	<h1><a id="wave-extensions-to-operational-transformation" name="wave-extensions-to-operational-transformation">Wave Extensions to Operational Transformation</a></h1>
	<p>A wave is a collection of wavelets. A wavelet contains a collection of documents.
	A document consists of a structured, XML-like document and some annotations.
	A wavelet is where concurrent modification takes place.
	A wavelet is the object on which OT is applied.</p>
	<div class="section">
	<h2><a id="clients-wait-for-acknowledgement-from-server-before-sending-more-operations" name="clients-wait-for-acknowledgement-from-server-before-sending-more-operations">Clients wait for acknowledgement from server before sending more operations</a></h2>
	<p>To recap, under the basic theory of OT, a client can send operations
	sequentially to the server as quickly as it can. The server can do the same.
	This means the client and server can traverse through the state space via
	different OT paths to the same convergent state, depending on when they receive
	the other parties' operations. See diagram below.</p>
	<img alt="img/ot-paths.png" src="img/ot-paths.png" />
	<p>When you have multiple clients connected to the server, every client and server
	pair have their own state space. One shortcoming of this is the server needs
	to carry a state space for every connected client, which can be
	memory-intensive. In addition, this complicates the server algorithm by
	requiring it to convert clients' operations between state spaces.</p>
	<p>Having a simple and efficient server is important in making waves reliable and
	scalable. With this goal, Wave OT modifies the basic theory of OT by requiring
	the client to wait for acknowledgement from the server before sending more
	operations. When a server acknowledges a client's operation, it means the
	server has transformed the client's operation, applied it to the server's copy
	of the wavelet and broadcast the transformed operation to all other connected
	clients. Whilst the client is waiting for the acknowledgement, it caches
	operations produced locally and sends them in bulk later.</p>
	<p>With the addition of acknowledgements, a client can infer the server's OT path.
	We call this the inferred server path. By having this, the client can send
	operations to the server that are always on the server's OT path.</p>
	<p>This has the important benefit that the server only needs to have a single
	state space, which is the history of operations it has applied. When it
	receives a client's operation, it only needs to transform the operation against
	the operation history, apply the transformed operation, and then broadcast it.</p>
	<img alt="img/david_ot3.png" src="img/david_ot3.png" />
	<p>One trade-off of this simplification is that a client will see chunks of operations
	from another client in intervals of approximately one round trip time to the
	other client. We believe the server-side benefits make this a worthwhile trade-off.</p>
	</div>
	</div>
	<div class="section">
	<h1><a id="wavelet-operations" name="wavelet-operations">Wavelet Operations</a></h1>
	<p>Wavelet operations consist of document operations, for modifying documents,
	and non-document operations, for tasks such
	as adding or removing a wavelet participant. We'll focus on document
	operations here.</p>
	<div class="section">
	<h2><a id="document-support" name="document-support">Document Support</a></h2>
	<p>A document operation has a streaming interface, similar to an
	XMLStreamWriter or a SAX handler. The document operation consists of a sequence
	of ordered document mutations. The mutations are applied in sequence as you
	traverse the document linearly.</p>
	<p>Designing document operations in this manner makes it easier to write the
	transformation function and composition function described later.</p>
	<p>A wave document can be regarded as a single
	document operation that can be applied to the empty document.</p>
	<p>In Google Wave, every character, start tag or end tag in a document is called an item. Gaps
	between items are called positions. Position 0 is before the first item. A
	document operation can contain mutations that reference positions. For example,
	a "Retain" mutation specifies how many positions to skip ahead in the
	document before applying the next mutation.</p>
	<img alt="img/doc-items.png" src="img/doc-items.png" />
	<p>Wave document operations also support annotations. An annotation is some
	meta-data associated with an item range, i.e., a start position and an end
	position. This is particularly useful for describing text formatting and
	spelling suggestions, as it does not unecessarily complicate the underlying structured
	document format.</p>
	<img alt="img/annotations.png" src="img/annotations.png" />
	<p>Wave document operations consist of the following mutation components:</p>
	<ul class="simple">
	<li>retain</li>
	<li>insert characters</li>
	<li>insert element start</li>
	<li>insert element end</li>
	<li>delete characters</li>
	<li>delete element start</li>
	<li>delete element end</li>
	<li>replace attributes</li>
	<li>update attributes</li>
	<li>annotation boundary</li>
	</ul>
	<p>The following is a more complex example document operation.:</p>
	<pre class="literal-block">
	retain 3
	insert element start with tag "p" and no attributes
	insert characters "Hi there!"
	insert element end
	retain 5
	delete characters 4
	retain 2
	</pre>
	<p>From this, one can see how an entire document can be represented as a
	single document operation.</p>
	</div>
	<div class="section">
	<h2><a id="transformation-function" name="transformation-function">Transformation Function</a></h2>
	<p>Representing document operations using a stream interface has the benefit that
	it makes processing operations in a linear fashion easy.</p>
	<img alt="img/transformation.png" src="img/transformation.png" />
	<p>The operation transformer works by taking two streaming operations as input,
	simultaneously processing the two operations in a linear fashion, and
	outputting two streaming operations. This stream-style processing ensures that
	transforming a pair of very large operations is efficient.</p>
	</div>
	<div class="section">
	<h2><a id="composition" name="composition">Composition</a></h2>
	<p>The document operations have been engineered so that they can be composed
	together and the composition of any two document operations that can be
	composed together is itself a single document operation.</p>
	<p>Furthermore, the composition algorithm processes operations as linear streams,
	so the composition algorithm is efficient.</p>
	<img alt="img/composition.png" src="img/composition.png" />
	<p>The composition B∙A has the property that (B∙A)(d) = B(A(d))
	for all documents d on which A can be applied.</p>
	<p>While a Wave client awaits server acknowledgement, it composes all its
	pending operations. This reduces the number of operations to transform
	and send.</p>
	</div>
	</div>
	<div class="section">
	<h1><a id="references" name="references">References</a></h1>
	<p>"Operational transformation". In Wikipedia, the free encyclopedia, May 28, 2009. <a class="reference" href="http://en.wikipedia.org/wiki/Operational_transformation">http://en.wikipedia.org/wiki/Operational_transformation</a></p>
	<p>David A. Nichols, Pavel Curtis, Michael Dixon, and John Lamping: <a class="reference" href="http://doi.acm.org/10.1145/215585.215706">High-latency, low-bandwidth windowing in the Jupiter collaboration system</a>, UIST '95: Proceedings of the 8th annual ACM symposium on User interface and software technology, pp.111-120. ACM, 1995.</p>
	</div>
	</div>
	</body>
	</html>