Hi David, 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 <[email protected]> wrote: > On Nov 19, 8:43 am, Daniel Paull <[email protected]> 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. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
