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?

• A.Schulz: Are you interested in developing such a system, or do you ask if a system that provides this functionality is known?
• Raphael: Have you looked into existing collarborative editors?
• Kile Kasmir Asmussen: @A.Schulz I am interested in ultimately developing such a system tailored to a specific purpose, but right now is Research only.
• Kile Kasmir Asmussen: @Raphael I am investigating Etherpad, but if I am not mistaken, there isn't a lot of open-source systems of this kind.
• Raphael: I have used Gobby myself, which is open source. There seem to be about handful of open-source collaborative editors, including Etherpad.

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)

• Kile Kasmir Asmussen: Thank you so much! This was the magical keyword I lacked.