title: How does Google Docs deal with editing collisions?
body: <p>I've been toying around with writing my own Javascript editor, with functionality similar to Google Docs (allowing multiple people to work on it at the same time). One thing I don't understand:</p>
  
  <p>Let's say you've got User A and User B connected directly to each other with a network delay of 10ms. I'm assuming the editor uses a diff system (as I understand Docs does) where edits are represented like "insert 'text' at index 3," and that diffs are timestamped and forced to apply chronologically by all clients.</p>
  
  <p>Let's start off with a document containing the text: "xyz123"</p>
  
  <p>User A types "abc" at the begining of the document at timestamp 001ms, while User B types "hello" between "xyz" and "123" at timestamp 005ms.</p>
  
  <p>Both users would expect the result to be: "abcxyzhello123," however, taking into account network delay:</p>
  
  <ul>
  <li>User B would receive User A's edits of "insert 'abc' at index 0" at time 011ms. In order to keep the chronological order, User B would undo User B's insertion at index 3, insert User A's "abc" at index 0,  then re-insert User B's insertion at index 3, which is now between "abc" and "xyz," thus giving "abchelloxyz123"</li>
  <li>User A would receive User B's edits of "insert 'hello' at index 3" at time 015ms. It would recognize that User B's insertion was done after User A's, and simply insert "hello" at index 3 (now between "abc" and "xyz"), giving "abchelloxyz123"</li>
  </ul>
  
  <p>Of course, "<strong>abchello</strong>xyz123" is not the same as "<strong>abc</strong>xyz<strong>hello</strong>123"</p>
  
  <p>Other than literally assigning each and every character its own unique ID, I can't imagine how Google would manage to solve this problem effectively.</p>
  
  <p>Some possibilities I've thought of:</p>
  
  <ul>
  <li>Tracking insertion points instead of sending indexes with diffs would work, except you would have the exact same problem if User B moved his insertion point 1ms before editing.</li>
  <li>You could have User B send some information with his diff, like "inserting after 'xyz'" so that User A could intelligently recognize this has happened, but what if User A inserts the text "xyz?"</li>
  <li>User B could recognize that this has happened (when it receives User A's diff and sees that it's a conflict), then send out a diff undoing User B's edits and a new diff that inserts User B's "hello" "abc".length index further right. The problem with this is (1) User A would see a "jump" in the text and (2) if User A keeps editing then User B would have to continuously fix its diffs - even the "fixer" diffs would be off and need to fix, exponentially increasing the complexity.</li>
  <li>User B could send along with its diff a property that the last timestamped diff it received was -005ms or something, then A could recognize that B didn't know about its changes (since A's diff was at 001ms) and do conflict resolution then. The issue is (1) all users timestamps will be slightly off, considering most computer clocks aren't accurate to the ms and (2) if there's a third User C with a 25ms lag with User A but a 2ms lag with User B, and User C adds some text between "x" and "y" at -003ms, then User B would use User C's edit as a reference point, but User A wouldn't know about User C's edit (and thus User B's reference point) until 22ms. I believe this could be solved if you used a common server to timestamp all edits, but that seems rather involved.</li>
  <li>You could give each character a unique ID, then work off of those IDs instead of indexes, but that seems like overkill...</li>
  </ul>
  
  <p>I'm reading through <a href="http://www.waveprotocol.org/whitepapers/operational-transform" rel="noreferrer">http://www.waveprotocol.org/whitepapers/operational-transform</a>, but would love to hear any and all approaches to fixing this problem.</p>