Thanks for your thoughts, Daniel. I've expanded into some more detail in response below.
(Please excuse me re-ordering your message slightly in my reply. I should re-order the points in the proposal too). On 8 July 2010 10:45, Daniel Paull <[email protected]> wrote: > > On Jul 5, 2:52 pm, Alex North <[email protected]> wrote: > > http://www.waveprotocol.org/design-proposals. > > Hi Alex, > > Regarding the "OT insertion order design proposal", I do not see why > this change would be necessary. Perhaps I'm tainted by having worked > with more general OT algorithms, but the order that results from > concurrent inserts at the same location is arbitrary - the only > requirement is that all sites need to agree on which order is chosen. > It is arbitrary to the protocol, yes. So given that, we want to pick an ordering that is most useful and natural for developers and provides the best behaviour for users of the applications like Wave for which we're using the protocol. I don't see why two users who both have operations that insert at the same position "in flight" at the same time are surprised to see the resulting inserts performed one order or the other. > ... Why is it desirable for "offline work" to come after the other operations? The proposal seems to be trying to imply some sort of temporal order to the concurrent operations - "later" inserts appear "after" earlier inserts. In the case of the offline work, there is a good chance that the offline work was performed, in wall- clock time, before the operations received by the server while the client was offline. Shouldn't the offline client therefore go first? It's advantageous for the document order of concurrent operations to match the temporal order because that's what people (users) expect. People are used to reading a document from top to bottom and having older content below newer content. New blips appear below old blips in the same thread; new replies to the same piece of content appear below old ones. It's arbitrary, but in this case we can improve the user experience by putting later content later. For flaky/offline clients it's not so much the wall-clock time that's relevant, but the context within which some content was written. When content is inserted earlier in the document it may change the meaning of later content. People assume that later (in the document) content was written within the context of earlier content. Now clearly a malicious user can always go and insert early content, but for the usual, well-behaved case things turn out more naturally if content which appears later (in time) appears later in the document. Online users, not familiar with the semantics of OT, would be surprised to see content logically inserted at the same place as some their own but arriving later appear above it rather than below it. We should strive not to surprise them, because (a) there's often more of them, as people just watching the wave will observe that behaviour too, and (b) the situation is not symmetric. Often the offline/flaky user *knows* that they are offline. It's less surprising to them to see concurrent content appear somewhere odd. An exemplary case of the oddness is appending blips to a thread in Google Wave. If two users concurrently append blips then they appear in some order and neither user is too surprised when it all happens within the space of a second. But if one user is temporarily offline then when they return their blip ends up above all blips created while they were offline. This is unexpected to everyone observing and may unintentionally change the meaning of existing blips. This behaviour could be fixed if the conversation model was implemented differently. As it is the structure of the conversation manifest mirrors the logical structure of the conversation. The lists of blips that form each thread are in top-down order and appending is modeled as as an insertion at the end of the list <thread> <blip id="first"/> <blip id="second"/> </thread> The concurrent behaviour could be fixed by reversing the order of the blips and threads in the manifest, and that's what is meant by "last is first". It's entirely my fault for not seeing this poor OT behaviour when designing the structure. If I'd realised, it would probably be backwards. But I hope you'll agree that that's an unnatural representation. Other developers building their own structures are likely to make the same mistake. The conversation manifest is not the only example, though for others (like tags) the ordering is less user-critical. Development and debugging is much easier when the data matches the conceptual model. <thread> <blip id="second"/> <blip id="first"/> </thread> The proposal states, "The last-is-first interpretation means data > structures need to be represented "backwards" in the document to have > desired transform. To create a list, appending to the list would be > implemented as inserting at position zero, like a stack." I don't > understand this at all. > > If I were building up a list by generating insert operations at > position zero, I should see the most recently inserted item at > position zero, not at the end of the list as you claim. This is > because subsequent operations are generated in the context of previous > operations, and as such, they are not be considered concurrent and > there is no collision of insertion points (this is basic causal order > stuff). > With the current OT, a list with "append" as the primary mutator should be represented backwards in the document, the first item last in the content, with the logical append being an insert-at-zero. This is opposite to the conceptual structure of the list where the first item appended is first in top-to-bottom order. > The classical approach is to use the site identifier to break the > tie. That is, there is a total order on sites and, say, the "lower" > site goes first. > Luckily we don't need to do that, and can instead use temporal order at the server to provide the most natural (for humans) ordering of content. I hope that sheds some more light on the reasons we're behind this proposal. -- 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.
