I've been trying to figure out how to do the collaboration part of real-time collaboration, and I've found a lot over the past week. I've been meaning to do an actual blog entry that tries to explain all the algorithms succinctly (but with examples), but in the mean-time, I've made a post on Quora with a short summary of what I've found: http://www.quora.com/What-are-good-frameworks-for-real-time-collaboration-in-a-web-application?__snid__=688223#answer_30021. If you don't know about Quora, it's an awesome new real-time Q&A site that has a lot of smart people answering questions. If you don't have an account on Quora, this is the paste of what I wrote:
Question: What are good frameworks for real-time collaboration in a web application?
I am probably going to go into more detail about this later, but in case people are curious, this is what I found. I've added links to articles that don't require an ACM subscription where I could. First, here are the possible algorithms you can use:
- Operational transformations. This is a term for a set of different algorithms that let you do real-time collaboration in a generic way. It's what Google Wave, Etherpad, and Subethaedit use. There are a few ways to implement this algorithm:
- A fully decentralized approach. This algorithm is described in the first real paper on real-time collaboration here: http://www.itu.dk/stud/speciale/.... The algorithm is a peer-to-peer way of doing things. The paper is actually very readable (coming from someone who gets easily intimidated by academia), but as far as I know, no real-time collaboration system actually implements this algorithm other than GROVE (though it is provably correct).
- Client-server model. The algorithm used here is much simpler than the one used for peer-to-peer collaboration, but requires you to have a central server that all the clients can talk to. This algorithm is described here: ftp://ftp.lambda.moo.mud.org/pub/MOO/p... . This paper is also very readable, though they do kind of skip over explaining how their model actually applies when you have multiple clients. I explain a bit more about how that actually works in my stack overflow answer here: http://stackoverflow.com/questio... .
- Google Wave approach. Wave actually uses the algorithm from b), with a slight change that allows them to reduce the amount of state the server needs to keep around. The Wave algorithm is described here: http://www.waveprotocol.org/whit.... It also has the advantage of being open source. If people aren't sure why their changes actually allow them to reduce the memory usage on a server, this is something I might expand upon later as it isn't the most obvious.
- Modification to Google Wave approach that doesn't introduce any latency into the network. The idea is to treat each client-server pair in a client-server model as a p2p network, and apply the algorithm from a). I made a post about it here: http://groups.google.com/group/wave-protocol/browse_thread/thread/8ffe6e7ab70d0ab. This is my own algorithm, and I haven't proven it, but it seems like it should work. It's more complicated than the Wave approach though and I probably wouldn't recommend actually using it.
- Differential synchronization. This is the algorithm used by Google Mobwrite and is described in more detail here: http://neil.fraser.name/writing/... . The idea behind this is to basically have "synchronization cycles" where diffs get sent to a server, merged there, and then the changes on the server get sent back to the client to get merged into the client's base. It's pretty simple to implement for plain-text, though thinking through how to do it for structured data, it seemed less easy.
- WOOT. It stands for "without operational transformations" and you can read more about it here: http://www.inria.fr/rrrt/rr-5580.... Instead of using diffs, WOOT sends a context for every action and each action is applied based on this context. It never deletes context, just marks things as hidden - so you can be sure that the context you use when sending an edit will exist.
- Total ordering of commands. This is the approach used by the Synchro library that builds on top of Google Wave: http://www.processwave.org/2010/.... With this approach, each client keeps around an array of actions it has taken that haven't yet been acknowledged by the server. When the client gets a new action, it reverts all of its unacknowledged actions, applies the new action, then re-applies its unacknowledged actions. For some subclass of applications, this can turn out to be simpler than a full operational transformation approach.
By the way, if you run across this paper while trying to find operational transformations (titled "An Updated Client-Server Real-time Collaborative Editor"), don't follow it: http://jcit.org/files/csc562-pro... . That algorithm does NOT work in all cases. I can provide details if people are interested.
If you don't want to implement these algorithms yourself, there are also a number of platforms that let you build real-time collaborative apps on top of them (as far as I know, they all use operational transformations to handle things generically). These include: 1) Google Wave
2) http://www.beweevee.com/
3) http://www.xtwip.com/
4) Probably others, but it seemed like they were mostly flash/silverlight/.NET/paid services, so I didn't look too much into it. Hope that helps!
