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 wave-protocol@googlegroups.com.
To unsubscribe from this group, send email to wave-protocol+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
> 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 wave-protocol@googlegroups.com.
> To unsubscribe from this group, send email to
> wave-protocol+unsubscribe@googlegroups.com<wave-protocol%2Bunsubscribe@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 wave-protocol@googlegroups.com.
To unsubscribe from this group, send email to wave-protocol+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
Tad, that link you posted is for the whole "Proceedings of the 8th
international conference on New technologies in distributed systems".
Which specific paper is the one you're talking about?
On Tue, May 4, 2010 at 3:25 AM, Tad Glines <tad.gli...@gmail.com> 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 <saik...@gmail.com>
> 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) 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 wave-protocol@googlegroups.com.
>> To unsubscribe from this group, send email to
>> wave-protocol+unsubscribe@googlegroups.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 wave-protocol@googlegroups.com.
> To unsubscribe from this group, send email to
> wave-protocol+unsubscribe@googlegroups.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 wave-protocol@googlegroups.com.
To unsubscribe from this group, send email to wave-protocol+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
> On Fri, Apr 30, 2010 at 9:24 PM, Saikat Chakrabarti <saik...@gmail.com>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 wave-protocol@googlegroups.com.
> > To unsubscribe from this group, send email to
> > wave-protocol+unsubscribe@googlegroups.com<wave-protocol%2Bunsubscribe@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 wave-protocol@googlegroups.com.
> To unsubscribe from this group, send email to wave-protocol+unsubscribe@googlegroups.com.
> 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 wave-protocol@googlegroups.com.
To unsubscribe from this group, send email to wave-protocol+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
> On May 3, 7:25 pm, Tad Glines <tad.gli...@gmail.com> 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 <saik...@gmail.com
> >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 wave-protocol@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > wave-protocol+unsubscribe@googlegroups.com<wave-protocol%2Bunsubscribe@goog legroups.com>
> <wave-protocol%2Bunsubscribe@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 wave-protocol@googlegroups.com.
> > To unsubscribe from this group, send email to
> wave-protocol+unsubscribe@googlegroups.com<wave-protocol%2Bunsubscribe@goog legroups.com>
> .
> > 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 wave-protocol@googlegroups.com.
> To unsubscribe from this group, send email to
> wave-protocol+unsubscribe@googlegroups.com<wave-protocol%2Bunsubscribe@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 wave-protocol@googlegroups.com.
To unsubscribe from this group, send email to wave-protocol+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
