How does real-time collaboration with multiple clients work in a system using operation transformations with a central server?

Question

I just finished reading High-Latency, Low-Bandwidth Windowing in the Jupiter Collaboration System and I mostly followed everything until part 6: global consistency. This part describes how the system described in the paper can be extended to accomodate for multiple clients connected to the server. However, the explanation is very short and essentially says the system will work if the central server merely forwards client messages to all the other clients. I don't really understand how this works though. What state vector would be sent in the message that is sent to all the other clients? Does the server maintain separate state vectors for each client? Does it maintain a separate copy of the widgets locally for each client?

The simple example I can think of is this setup: imagine client A, server, and client B with client A and client B both connected to the server. To start, all three have the state object "ABCD". Then, client A sends the message "insert character F at position 0" at the same time client B sends the message "insert character G at position 0" to the server. It seems like simply relaying client A's message to client B and vice versa doesn't actually handle this case. So what exactly does the server do?

Andreas

Answer 1

I actually figured out how this would work. In my example, server keeps a state space for both client A and client B. In the case where server gets client A's message first, the server gets the message with state vector (0, 0), inserts F, then updates its state vectors to be (1, 0) and (0, 1) for A and B, respectively (where the first number is the number of messages from the client that have been processed and the second is the number of messages from the server that have been processed). The server then sends "insert F at position 0" with state vector (0, 0) (since this was the state of the server in B's state space when the message was received by the server) and gets "insert G at position 0" from B sent with state (0, 0). Since the server is in state (0, 1) in B's state space, it first transforms the message (and similarly, since B is in (1, 0) when it receives the server's message, it also transforms the message it got from the server). Because transformations must be setup so that if xform(c, s) = (c', s') then c' applied to s equals s' applied to c, B and the server end up in the same state. The same happens with the message the server received from B and then sends to A.

Andreas

For posterity, in case this wasn't clear: the server acts as a "proxy client" between A and B, translating an op from A (a) into a', and forwards op a' to B (as if the server itself generated the op). The server, then, has copies of both A and B operation queues, whereas A and B only have a copy of the server operation queue. For further reading, check out Concurrency Control in Groupware Systems, and A Counterexample to the Distributed Operational Transform and a Corrected Algorithm for Point-to-point Communication. – Proboscidean