In doing my own research into OT algorithms I ran across this paper on ACM ( http://portal.acm.org/toc.cfm?id=1416729&coll=Portal&dl=Portal&type=proceeding&CFID=88950358&CFTOKEN=25433261) that seems to propose an OT algorithm that satisfies TP2 without the need for individual client state vectors.
-Tad On Fri, Apr 30, 2010 at 9:24 PM, Saikat Chakrabarti <[email protected]>wrote: > 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 <http://portal.acm.org/%0Acitation.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]<wave-protocol%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/wave-protocol?hl=en. > > -- 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.
