I've been reading the various wave protocol white papers and wanted to
understand more about how the OT implementation employed by Wave
differs from that described in the Jupiter paper. In particular, the
use of server Acknowledgements as noted in the OT white paper:
"Having a simple and efficient server is important in making Wave
reliable and scalable. With this goal, Wave OT modifies the basic
theory of OT by requiring the client to wait for acknowledgement from
the server before sending more operations. When a server acknowledges
a client's operation, it means the server has transformed the client's
operation, applied it to the server's copy of the Wavelet and
broadcasted the transformed operation to all other connected clients.
Whilst the client is waiting for the acknowledgement, it caches
operations produced locally and sends them in bulk later."
I checked out the Fedone code and started digging to try and find
where the client caches operation while waiting for an
acknowledgement, but the code that does this has not jumped out at
me. Looking at ConsoleClient.java, it seems that operations are sent
to the server without any handshaking with the server at all. This
can be seen when sendAppendMutation() is called in response to user
input, which in turn calls backend.sendWaveletDelta(), which invokes
submitRequest() on the server. I could not find any code relating to
acknowledgements in the server side code either.
Is the server acknowledgement and operation caching in the client not
implemented in the Fedone example? If it is, can someone please point
me in the right direction.
No, the FedOne client doesn't wait for acknowledgement before sending the
next operation -- it hasn't been an issue until recently. There is now a
patch in review for implementing this, see
http://codereview.waveprotocol.org/23002/show.
On Thu, Nov 19, 2009 at 12:52 AM, Daniel Paull <monaro...@gmail.com> wrote:
> Hello All,
> I've been reading the various wave protocol white papers and wanted to
> understand more about how the OT implementation employed by Wave
> differs from that described in the Jupiter paper. In particular, the
> use of server Acknowledgements as noted in the OT white paper:
> "Having a simple and efficient server is important in making Wave
> reliable and scalable. With this goal, Wave OT modifies the basic
> theory of OT by requiring the client to wait for acknowledgement from
> the server before sending more operations. When a server acknowledges
> a client's operation, it means the server has transformed the client's
> operation, applied it to the server's copy of the Wavelet and
> broadcasted the transformed operation to all other connected clients.
> Whilst the client is waiting for the acknowledgement, it caches
> operations produced locally and sends them in bulk later."
> I checked out the Fedone code and started digging to try and find
> where the client caches operation while waiting for an
> acknowledgement, but the code that does this has not jumped out at
> me. Looking at ConsoleClient.java, it seems that operations are sent
> to the server without any handshaking with the server at all. This
> can be seen when sendAppendMutation() is called in response to user
> input, which in turn calls backend.sendWaveletDelta(), which invokes
> submitRequest() on the server. I could not find any code relating to
> acknowledgements in the server side code either.
> Is the server acknowledgement and operation caching in the client not
> implemented in the Fedone example? If it is, can someone please point
> me in the right direction.
This would solve a major issue I have with QWaveClient currently. My client
already caches submits, however, it was until now impossible to tell which
ProtocolWaveletUpdate corresponds to my ProtocolSubmitRequest.
I solved this by inspecting the delta's author, but this failes obviously
when the same user connects twice.
I hope that this change will show up in the main branch soon.
> No, the FedOne client doesn't wait for acknowledgement before sending the
> next operation -- it hasn't been an issue until recently. There is now a
> patch in review for implementing this, see
> http://codereview.waveprotocol.org/23002/show.
> -- Ben
> On Thu, Nov 19, 2009 at 12:52 AM, Daniel Paull <monaro...@gmail.com>wrote:
>> Hello All,
>> I've been reading the various wave protocol white papers and wanted to
>> understand more about how the OT implementation employed by Wave
>> differs from that described in the Jupiter paper. In particular, the
>> use of server Acknowledgements as noted in the OT white paper:
>> "Having a simple and efficient server is important in making Wave
>> reliable and scalable. With this goal, Wave OT modifies the basic
>> theory of OT by requiring the client to wait for acknowledgement from
>> the server before sending more operations. When a server acknowledges
>> a client's operation, it means the server has transformed the client's
>> operation, applied it to the server's copy of the Wavelet and
>> broadcasted the transformed operation to all other connected clients.
>> Whilst the client is waiting for the acknowledgement, it caches
>> operations produced locally and sends them in bulk later."
>> I checked out the Fedone code and started digging to try and find
>> where the client caches operation while waiting for an
>> acknowledgement, but the code that does this has not jumped out at
>> me. Looking at ConsoleClient.java, it seems that operations are sent
>> to the server without any handshaking with the server at all. This
>> can be seen when sendAppendMutation() is called in response to user
>> input, which in turn calls backend.sendWaveletDelta(), which invokes
>> submitRequest() on the server. I could not find any code relating to
>> acknowledgements in the server side code either.
>> Is the server acknowledgement and operation caching in the client not
>> implemented in the Fedone example? If it is, can someone please point
>> me in the right direction.
>> Thanks,
>> Dan
-- ---------------------------
Prof. Torben Weis
Universitaet Duisburg-Essen
torben.w...@gmail.com
Thank you for the link to the patch. I will certainly have a look at
this. Can you elaborate on what problems were found when not using
the server acknowledgement (is there a discussion thread somewhere on
this? I couldn't find one.)
One thing that is not clear from the Google Wave white paper on OT is
when acknowledgements are sent from the server to the client. What
I'd like to determine is if operations are sent from a number of
clients to the server concurrently, or, does the server make clients
take turns in sending operations to the server. Though I haven't done
the math yet, I would expect that if clients send operations
concurrently to the server and the server maintains only a single
state space, then the OT transformation functions would need to
satisfy TP2 (which is avoided in the Jupiter system). If I'm not
right here, are there any resources around that formally prove
correctness in the OT approach of Wave that I can read?
Cheers,
Dan
On Nov 18, 10:55 pm, Ben Kalman <btkal...@gmail.com> wrote:
> No, the FedOne client doesn't wait for acknowledgement before sending the
> next operation -- it hasn't been an issue until recently. There is now a
> patch in review for implementing this, seehttp://codereview.waveprotocol.org/23002/show.
> -- Ben
> On Thu, Nov 19, 2009 at 12:52 AM, Daniel Paull <monaro...@gmail.com> wrote:
> > Hello All,
> > I've been reading the various wave protocol white papers and wanted to
> > understand more about how the OT implementation employed by Wave
> > differs from that described in the Jupiter paper. In particular, the
> > use of server Acknowledgements as noted in the OT white paper:
> > "Having a simple and efficient server is important in making Wave
> > reliable and scalable. With this goal, Wave OT modifies the basic
> > theory of OT by requiring the client to wait for acknowledgement from
> > the server before sending more operations. When a server acknowledges
> > a client's operation, it means the server has transformed the client's
> > operation, applied it to the server's copy of the Wavelet and
> > broadcasted the transformed operation to all other connected clients.
> > Whilst the client is waiting for the acknowledgement, it caches
> > operations produced locally and sends them in bulk later."
> > I checked out the Fedone code and started digging to try and find
> > where the client caches operation while waiting for an
> > acknowledgement, but the code that does this has not jumped out at
> > me. Looking at ConsoleClient.java, it seems that operations are sent
> > to the server without any handshaking with the server at all. This
> > can be seen when sendAppendMutation() is called in response to user
> > input, which in turn calls backend.sendWaveletDelta(), which invokes
> > submitRequest() on the server. I could not find any code relating to
> > acknowledgements in the server side code either.
> > Is the server acknowledgement and operation caching in the client not
> > implemented in the Fedone example? If it is, can someone please point
> > me in the right direction.
On Thu, Nov 19, 2009 at 10:47 AM, Daniel Paull <monaro...@gmail.com> wrote:
> hi Ben,
> Thank you for the link to the patch. I will certainly have a look at > this. Can you elaborate on what problems were found when not using > the server acknowledgement (is there a discussion thread somewhere on > this? I couldn't find one.)
In the case of FedOne, this was causing a problem when Echoey was added to a wave with a user on wavesandbox. Unlike prior FedOne usage, these deltas come very quickly due to the real time character transmission. Echoey was replying to deltas without the response coming back, such that its echoed deltas were being submitted at the wrong version (confusing FedOne and corrupting the wave).
(This is actually part of a different patch I was working on which fixed Echoey to work with wavesandbox. Once this patch is submitted, I'll put the other out for review too).
> One thing that is not clear from the Google Wave white paper on OT is > when acknowledgements are sent from the server to the client. What > I'd like to determine is if operations are sent from a number of > clients to the server concurrently, or, does the server make clients > take turns in sending operations to the server. Though I haven't done > the math yet, I would expect that if clients send operations > concurrently to the server and the server maintains only a single > state space, then the OT transformation functions would need to > satisfy TP2 (which is avoided in the Jupiter system). If I'm not > right here, are there any resources around that formally prove > correctness in the OT approach of Wave that I can read?
I am not an expert on OT so I can't answer the second part of the question, but as to the first, yes clients are permitted (you might even say encouraged) to submit concurrently to the server.
(There is of course concurrency control inside the wave server to prevent race conditions arising from this...)
Again, not an expert in the academic side of OT: but, the only simplification we employ (and I suspect this is just a limitation of our optimistic client) is that each client only has one delta (i.e. set of operations) 'in-flight' at any one time. However, there's no limit on the number of submissions from different clients. Each delta is still applied in some timing-related order: one delta will always be before or after other deltas, never 'on top'.
On Thu, Nov 19, 2009 at 10:47, Daniel Paull <monaro...@gmail.com> wrote: > One thing that is not clear from the Google Wave white paper on OT is > when acknowledgements are sent from the server to the client. What > I'd like to determine is if operations are sent from a number of > clients to the server concurrently, or, does the server make clients > take turns in sending operations to the server. Though I haven't done > the math yet, I would expect that if clients send operations > concurrently to the server and the server maintains only a single > state space, then the OT transformation functions would need to > satisfy TP2 (which is avoided in the Jupiter system). If I'm not > right here, are there any resources around that formally prove > correctness in the OT approach of Wave that I can read?
I'll have to think about this a bit more, but I can see that the usual
TP2 puzzles do not apply in the wave case, even when multiple clients
submit changes to the server concurrently as the server ensures that
all clients see all changes in a consistent order. The common TP2
puzzles occur when operations are received in different orders at
nodes in a peer-to-peer network.
The part I'm not sure about though, is the claim that only a single
state space is used by the server and how this relates to when
acknowledgements are sent from the server to the client. In the end
I'm trying to think about whether the introduction of the server
acknowledgement means that latency between clients (ie, how long it
takes operations performed on one client to be seen on another) is
related to the number of concurrent operations performed by clients.
The OT white paper claims that the latency is constant, though it does
not specifically talk about concurrent operations by clients when
making that claim.
Cheers,
Dan
On Nov 19, 9:17 am, Sam Thorogood <sam.thorog...@gmail.com> wrote:
> Again, not an expert in the academic side of OT: but, the only
> simplification we employ (and I suspect this is just a limitation of
> our optimistic client) is that each client only has one delta (i.e.
> set of operations) 'in-flight' at any one time. However, there's no
> limit on the number of submissions from different clients. Each delta
> is still applied in some timing-related order: one delta will always
> be before or after other deltas, never 'on top'.
> On Thu, Nov 19, 2009 at 10:47, Daniel Paull <monaro...@gmail.com> wrote:
> > One thing that is not clear from the Google Wave white paper on OT is
> > when acknowledgements are sent from the server to the client. What
> > I'd like to determine is if operations are sent from a number of
> > clients to the server concurrently, or, does the server make clients
> > take turns in sending operations to the server. Though I haven't done
> > the math yet, I would expect that if clients send operations
> > concurrently to the server and the server maintains only a single
> > state space, then the OT transformation functions would need to
> > satisfy TP2 (which is avoided in the Jupiter system). If I'm not
> > right here, are there any resources around that formally prove
> > correctness in the OT approach of Wave that I can read?
> I'll have to think about this a bit more, but I can see that the usual
> TP2 puzzles do not apply in the wave case, even when multiple clients
> submit changes to the server concurrently as the server ensures that
> all clients see all changes in a consistent order. The common TP2
> puzzles occur when operations are received in different orders at
> nodes in a peer-to-peer network.
> The part I'm not sure about though, is the claim that only a single
> state space is used by the server and how this relates to when
> acknowledgements are sent from the server to the client. In the end
> I'm trying to think about whether the introduction of the server
> acknowledgement means that latency between clients (ie, how long it
> takes operations performed on one client to be seen on another) is
> related to the number of concurrent operations performed by clients.
> The OT white paper claims that the latency is constant, though it does
> not specifically talk about concurrent operations by clients when
> making that claim.
My understanding of the Google Wave Protocol only comes from briefly
reading their white paper on OT. I hope the following is accurate:
Consider there is one server and 3 clients that all start in the same
initial state (i.e. from quiescence). Let the server already contain
n operations in its linear history buffer (HB). Let the 3 clients
concurrently generate operations O1,O2,O3 respectively. This leads to
the cube picture with the 3 operations extending out from a common
starting point.
In a system that satisfies TP2, all paths around the cube must
converge on the opposite corner. A system that avoids TP2 does so by
constraining the path that is taken. For example in the Google Wave
Protocol the server may happen to add the operations to its linear HB
in the order O1,O3,O2. This order probably depends on the order in
which the operations happen to have been received from the clients –
even though they were roughly sent in parallel.
Each time the server receives an operation it is always able to IT the
operation against some tail of its linear HB. For example when O2
arrives it will specify sequence number n which is the number of
operations in the server HB that are in its context. The server will
IT against the tail [begin()+n,end()) which in this scenario will be
[O1, O3’] where O3’ = IT(O3,O1). In fact for that reason the Google
Wave protocol is able to use simple sequence numbers instead of vector
times.
When a server wants to update a client (which it is allowed to do at
any time), it simply sends the tail of its HB which it knows that the
client doesn’t yet have. This is very deterministic because the
client isn’t allowed to receive operations from any other machine.
For example the client that sent O1 could be sent the tail [O3’, O2’]
where O2’ = IT( O2, [O1, O3’] ) ]. Note that it would be possible to
only send O3’ (when it was first appended to the HB). The server can
be very aggressive in sending its operations out to clients. It is
always possible for a client to IT the received operations against the
list of local operations that have not yet been sent to the server
(and the client has not been allowed to send these to the server
yet). This indeed is why the client must wait.
Note BTW that Rui Li and Du Li point out that any system that doesn’t
meet TP2 doesn’t actually preserve intention correctly in certain
cases. It is possible that these examples don’t occur frequently
enough to be considered a problem in practise.
Thanks for posting. Background for others - I discussed this issue
with David today and asked him to post his response here as it
certainly helped me understand the Wave OT algorithms better.
After much discussion today, I am sure I understand how the server
acknowledgements fit into the scheme of things and am convinced that
the the use of server acks does not imply that latency is proportional
to the number of concurrent operations performed by clients. I must
say though, the OT white paper is not as clear as it could be in some
regards. I'll try to write up my thoughts on this at some point to
help others who might be trying to understand the differences between
Wave and Jupiter.
Cheers,
Dan
On Nov 19, 12:11 pm, David BL <david.barrettlenn...@gmail.com> wrote:
> On Nov 19, 8:43 am, Daniel Paull <monaro...@gmail.com> wrote:
> > I'll have to think about this a bit more, but I can see that the usual
> > TP2 puzzles do not apply in the wave case, even when multiple clients
> > submit changes to the server concurrently as the server ensures that
> > all clients see all changes in a consistent order. The common TP2
> > puzzles occur when operations are received in different orders at
> > nodes in a peer-to-peer network.
> > The part I'm not sure about though, is the claim that only a single
> > state space is used by the server and how this relates to when
> > acknowledgements are sent from the server to the client. In the end
> > I'm trying to think about whether the introduction of the server
> > acknowledgement means that latency between clients (ie, how long it
> > takes operations performed on one client to be seen on another) is
> > related to the number of concurrent operations performed by clients.
> > The OT white paper claims that the latency is constant, though it does
> > not specifically talk about concurrent operations by clients when
> > making that claim.
> My understanding of the Google Wave Protocol only comes from briefly
> reading their white paper on OT. I hope the following is accurate:
> Consider there is one server and 3 clients that all start in the same
> initial state (i.e. from quiescence). Let the server already contain
> n operations in its linear history buffer (HB). Let the 3 clients
> concurrently generate operations O1,O2,O3 respectively. This leads to
> the cube picture with the 3 operations extending out from a common
> starting point.
> In a system that satisfies TP2, all paths around the cube must
> converge on the opposite corner. A system that avoids TP2 does so by
> constraining the path that is taken. For example in the Google Wave
> Protocol the server may happen to add the operations to its linear HB
> in the order O1,O3,O2. This order probably depends on the order in
> which the operations happen to have been received from the clients –
> even though they were roughly sent in parallel.
> Each time the server receives an operation it is always able to IT the
> operation against some tail of its linear HB. For example when O2
> arrives it will specify sequence number n which is the number of
> operations in the server HB that are in its context. The server will
> IT against the tail [begin()+n,end()) which in this scenario will be
> [O1, O3’] where O3’ = IT(O3,O1). In fact for that reason the Google
> Wave protocol is able to use simple sequence numbers instead of vector
> times.
> When a server wants to update a client (which it is allowed to do at
> any time), it simply sends the tail of its HB which it knows that the
> client doesn’t yet have. This is very deterministic because the
> client isn’t allowed to receive operations from any other machine.
> For example the client that sent O1 could be sent the tail [O3’, O2’]
> where O2’ = IT( O2, [O1, O3’] ) ]. Note that it would be possible to
> only send O3’ (when it was first appended to the HB). The server can
> be very aggressive in sending its operations out to clients. It is
> always possible for a client to IT the received operations against the
> list of local operations that have not yet been sent to the server
> (and the client has not been allowed to send these to the server
> yet). This indeed is why the client must wait.
> Note BTW that Rui Li and Du Li point out that any system that doesn’t
> meet TP2 doesn’t actually preserve intention correctly in certain
> cases. It is possible that these examples don’t occur frequently
> enough to be considered a problem in practise.
Please feel free to contact me regarding errors and omission in what I
have written. I hope to write more about Wave client/server OT
implementation when I find some time.
Cheers,
Dan
On Nov 19, 10:59 pm, Daniel Paull <monaro...@gmail.com> wrote:
> Thanks for posting. Background for others - I discussed this issue
> with David today and asked him to post his response here as it
> certainly helped me understand the Wave OT algorithms better.
> After much discussion today, I am sure I understand how the server
> acknowledgements fit into the scheme of things and am convinced that
> the the use of server acks does not imply that latency is proportional
> to the number of concurrent operations performed by clients. I must
> say though, the OT white paper is not as clear as it could be in some
> regards. I'll try to write up my thoughts on this at some point to
> help others who might be trying to understand the differences between
> Wave and Jupiter.
