Yes, that's the one. On Mon, May 3, 2010 at 7:39 PM, Saikat Chakrabarti <[email protected]>wrote:
> 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%[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]<wave-protocol%[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]<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.
