Synchronization / collaborative editing algorithm

gistfile1.txt

This is a collaborative editing protocol I came up with. Like OT, it
is change-based, not diff-based. But it is much easier to verify that
clients end up converging, because they all end up applying the
modifications in the same order (so that they _have to converge_, if
they are using the same algorithm).


Clients start with same version + version number

When a client makes a change, that is locally applied and a description
is buffered in a list of unconfirmed changes.

The client sends its unconfirmed changes, along with the version number
at which they start, to the server.

When the server's current version number matches that number, they are
accepted and broadcast to other clients.

If not, they are rejected.

This means the server has changes the client has not received yet. So
it waits for them.

When they arrive, the client 'rebases' its unconfirmed changes on top of
the newly received changes.

And tries to send them to the server again.

(When changes arrive and there are no local unconfirmed changes, they are
simply applied, syncing the client's version.)