What sort of algorithm/communication model/data structure do collaborative real time editors use?

Question

I am researching collaborative editing systems for some work, but so far my search is turning up blank.

Collaborative real-time editing systems almost all have features like:

• Many users can edit the document at the same time
• All changes are dated and saved in a linear revision history
• Edits are visible in semi-real time
• Who-wrote-what is tracked for all content

I cannot think of a data- and procedure model to encompass all of these without huge inefficiencies, for example:

• Take user input as a few typestrokes at a time, thus enabling real-time visibility but with horrible server loads.
• Take user input as element changes, thus disabling real-time visibility and complicating many-user-editing of one paragraph.
• Edit a XML Document Model Object in place responding to inputs, but making it difficult to version/revision track.
• Edit linear text stored in an appropriate editing structure responding to inputs, making it difficult to verify that correct markup is being generated.
• Store revision history accumulating, requiring computational resources but easing on space.
• Store revision history whole, requiring space but easing on computation.

Am I off track? Does there exist good solutions to these problems? What, if any, is the relevant litterature?

Answer 1

The usual approach is operational transformation. The wikipedia page seems to be pretty good. Here are some other references:

• Understanding and Applying Operational Transformation
• Operational Transformation: An Introduction
• OT FAQ
• ShareJS - javascript library implementing OT

Here's a paper on a different approach: Real time group editors without operational transformation. (Note: I haven't actually read it, so can't speak to how good it is)