Is the specific paper you are talking about this one: http://portal.acm.org/citation.cfm?id=1416729.1416781&coll=Portal&dl=Portal&idx=1416729&part=&WantType=&title=New%20technologies%20in%20distributed%20systems&CFID=88950358&CFTOKEN=25433261 ? That page has a bunch of papers on it.
On May 3, 7:25 pm, Tad Glines <[email protected]> wrote: > 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=p...) > 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%2bunsubscr...@goog > > legroups.com> > > . > > 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 > athttp://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.
