W00T (Without Operational Transformation)
This paper describes a method of building online collaborative systems that is far simpler than OT. A few years ago I would have dismissed it as a hack (a key to its implementation strategy is that it never deletes characters from the document). But a few years of experience in software engineering have taught me to appreciate it's simplicity in implementation. Simple implementation and "good enough" feature set is sometimes the right move.
It's pretty easy reading as far as academic papers go. It's full of examples to make sure that you really know the edge cases of the algorithm by the time you're done reading.
Below is a gif of my own (toy) implementation. The code is on Github here.
More than you want to know about @synchronized
If you've done any concurrent programming in Objective-C, then you've seen the
@synchronizedconstruct does just what a lock does: it prevents different threads from executing the same code at the same time. But it's more convenient and more readible in some cases compared to allocating, locking and unlocking an
If you've never usedRead more...
@synchronizedbefore, below is an example of how to use it. The meat of this article will talk about a short investigation that I made into how
An Intro to OT
I've been trying to learn about real-time collaborative editing. One common approach is operational trasnformation (OT) algorithms, and most OT resources online reference Nichols, David A., et al. "High-latency, low-bandwidth windowing in the Jupiter collaboration system.".
That paper one of the first to introduce OT as a technique for building collaborative editors. It's pretty light on implementation details and spends more time than I'd like describing what real-time collaboration is (I guess you couldn't take that for granted in 1995). It's an interesting read, but if you're interested in getting started with OT, I'd recommend starting instead with this article by Daniel Spiewak. It describes the OT algorithm at a high level and gets into some of the complexities of using it to build an OT server/client.
When I was done with Spiewak's article, I still didn't have a solid idea of how to implement OT on text or XML or any particular datatype. He directs to you to the Google Wave whitepapers to find out more, but I found the ot.py implementation to be a better explanation. It's pretty small and easy to read in entirety. There are more implementations at that link (js, Haskell, lua) but I haven't dug into them. If you find one that you think is great, let me know!
If you draw any quad and join its midpoints with lines, you get a parallelogram! That's pretty neat. The animation below repeatedly draws a (not quite) random quad and joins its midpoints with lines.