evan_tech

Previous Entry Share Next Entry
03:18 pm, 10 May 08

concurrent editing

While I'm on the subject of concurrent editing:

My reading group read Designing a commutative replicated data type a few months ago. The basic idea I've retained from the paper (is has been some months) is that one way to avoid conflicts is to design your data representation such that conflicts are impossible by making all operations commute, demonstrating the theory by presenting a design for a multiuser simultaneous editor. ("Like SubEthaEdit" is what I kept saying to people, but apparently few people I know have heard of it.) By representing positions within the buffer as adddresses related to characters you currently know about, and having a globally-defined resolution strategy for two edits to the same position, you can safely allow edits to come in from clients in any order and maintain consistent state.

(Commuting operaitons sounds like darcs, doesn't it? In fact, this fellow was discussing darcs's patch theory in connection to concurrent editing, though I suspect ultimately it's the wrong model...)

The paper's really pretty clever in a bunch of ways (like: how do you make a globally-consistent addressing scheme in the presence of simultaneous edits?) and a friend and I sat down to implement it as a web app with a bunch of Javascript. I had planned to target the release of App Engine but the lack of Comet (again, that bites me) sorta turned me off to the whole idea. And I have so many other projects I ought to be finishing first... He, however, powered on to get something that seems to mostly work but is a bit on the inefficient side.

PS If you're curious, the model Gobby uses (Gobby is another simultaneous editor) is described here. It's again the "hope we update often enough that there's no conflict" design I mentioned in the previous post.