I have been reading up on operational transformation (as well as other methods for doing real-time collaborative work) and came across the Google Wave white paper. I understand the motivation for the extension (having clients wait for acks before sending more actions), but wanted to propose a different algorithm that achieves the same goal of low server overhead without the need for added latency. I'm not seriously proposing using this in Wave, but more just want to see what others thought of it (not sure what other forums there are to talk about things like this, after all) and if there are any obvious flaws with it.
My motivation for this algorithm comes from combining the ideas presented in the original groupware paper (http://portal.acm.org/ citation.cfm?id=66963) with a client-server model as described in the Jupiter paper(ftp://ftp.lambda.moo.mud.org/pub/MOO/papers/ JupiterWin.ps). In my proposed algorithm, the server maintains one stack of all operations that have been executed. Each operation on the stack also has a state vector attached to it where the state vector may be <Na, Nb, Nc> where Na is the number of operations the server had processed from client a at the time this message was added to the server's stack, Nb is the number of messages from client b, etc. It additionally has an integer per client indicating the number of total messages it has processed from the client. Additionally, each client keeps a log of all operations it gets from the server (like in Ellis' p2p algorithm) as well as a state vector indicating the number of operations the client has generated and the number of operations from the server it has received for each operation in its log. Now both the client and server implement the algorithm described on page 6 of Ellis' groupware algorithm (screenshot from the paper: http://imgur.com/og7uF.png) with these important distinctions: 1) When the server receives a message from C, the "state vectors" that the server uses when doing comparisons against its log is just a comparison of the state vectors <Si, Ci> with <Sj, Cj>. Here, Si is the number of total operations the server has executed from any client at the time of the message in the log, Ci is the number of operations from C that the server has executed, Sj is the number of of operations from the server that C has processed when it produced its message, and Cj is the number of operations that C had produced when it sent out this latest message. 2) There is no need for priorities. 3) Causality is also a given since communication is ever occurring between a client and a server (given that the connection is over FIFO, and TCP/IP/HTTP is). I'm basically proposing a client-server model where each client/server pair thinks it is in a peer-to-peer network. And then, I am adapting a simplified algorithm proposed in "Concurrency control in groupware systems" to manage the communication between each client/server pair. This requires less memory than the Jupiter system, though slightly more than Wave's current approach (since we need to store an extra state vector that increases with number of clients for each operation). It has the benefit of having less latency than Wave's approach though. Does anyone see any flaws with this algorithm? Is the main downside of this algorithm just the complexity of implementing it? Any other thoughts about it? Thanks, Saikat -- You received this message because you are subscribed to the Google Groups "Wave Protocol" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
