On Mon, Apr 29, 2013 at 8:56 PM, Nico Williams <n...@cryptonector.com> wrote: > BTW, this has all been solved before (clearly). Research it and use > whatever protocol pattern is most appropriate (or, if you can't > because of patents, invent a new protocol). > > Some posts on this list pointed at some such prior work.
I recently implemented a simple collaborative text editor focusing on maintaining consistency across multiple users edits. I have been following the discussion about the consistency related issues and there are indeed several possible approaches. I will try to briefly describe mine and you can comment about its (in)feasibility. The main difference is that I was using a coordinating server, but I believe centralized steps can be turned into distributed ones. The edits are only of types "insert text" or "delete text", represented as (global-offset, type, data), where global-offset is the offset from the beginning of the document (I intentionally avoided dealing with paragraphs operations explicitly) and data is the inserted string (including line breaks) or the number of characters to delete from that position, depending on the edit type. A "document revision" is a document state (identified by an integer) which all users know and agree upon. A user state is the latest known revision and a set of new own edits, in which all offsets are calculated relative to this last revision. Periodically, the server asks for creating a new revision in which all users share their own edits, which can be merged for efficiency (e.g., put many consecutive insertions/deletions into a single edit). To generate a new revision from a set of edits, you have to incrementally apply each of them (to the last revision) sorted by increasing offsets, keeping track of how many characters you have added/removed so far to be able to pinpoint the correct location to apply. The main advantages of this approach are simplicity and avoid dealing with locking, conflicts, etc. As someone mentioned, when two users are editing too close to each other, there is no correct result for this. As a drawback, clients need to keep track of the latest document revision: if one misses a revision (the user leaves but the document keeps being edited by others), he should ask someone for the whole document. Regards, Marcelo