On Feb 28, 3:22 am, Tad Glines <[email protected]> wrote: > > Consider the following scenario. There is a document whose current > > state is "X". Three clients concurrently generate operations against > > this document as follows: > > > Client 1: insert "A" before the "X" > > Client 2: insert "B" after the "X" > > Client 3: delete the "X" > > > I'm sure that everyone will agree that the final document state must > > be "AB" if the intention of the users is to be preserved. > > > There are six possible orders that the server could apply these > > operations; two of them may give unexpected results! If the server > > decided to apply delete operation first, then the two inserts, once > > transformed to include the effect of the delete, will appear to be > > concurrent inserts at the same position. In the literature, the site > > identifier is used to break this tie, meaning that half the time the > > result final state will "AB" and half the time it will be "BA". Wave > > doesn't use site identifiers, but rather, relies on the order that the > > server chooses for these inserts - this still leads to "BA" half the > > time. > > > What is described above is a classic TP2 puzzle. In a peer-to-peer > > system this would represent divergence amongst peers. In wave it just > > gives a plain weird result. I see it as not preserving the intention > > of the users. > > While in one of the 6 cases wave would produce "BA" instead of "AB" all > clients would converge on the same result. So no divergence would occur as > it would in many TP2 systems. > And though wave would produce "BA" in some cases I don't think there is a > loss of intention. Client 1 could not possibly have "intended" to insert "A" > before "B" since there is no way for client 1 to know about client 2's > intention. Both client 1 and 2 intended to insert a character. Those > characters are inserted and they both get inserted adjacent to the position > of X.
When you say "Client 1 could not possibly have "intended" to insert "A" before "B" since there is no way for client 1 to know about client 2's intention." I disagree. They both knew about "X", so if you're intention talks about "inserting before (or after) X", then the transformations should be able to deduce that "A is before X and B is after B, therefore, A is before B". When a users inserts B after the X, you don't think they mean "Insert B after X and all other characters inserted before X"? Since A was inserted before X, it should definitely come before the B. You surely can't disagree with this. Perhaps to be a little stronger, I believe that when a user inserts B after X for a given document "XY", then the user means "Insert B after X and before Y and after all other characters inserted before X and before all other characters inserted after Y". I think this is the intent of the user and we should aim to preserve it. > BTW, in "*An analysis of intention preservation in group editors" Du Li and > Rui Li *seek to formalize the definition of intention preservation. The DOI > is:http://doi.acm.org/10.1145/1281100.1281166 > > Also, in "*Decentralized concurrency control for real-time collaborative > editors*" Abdessamad Imine appears to have solved the TP2 puzzle and done so > without the need for vector clocks. > DOI:http://doi.acm.org/10.1145/1416729.1416781 I don't think I've read this one (Abdessamad's), so I will check it out. > I'm not sure if Abdessamad's work is state of the art or if there has been > more advances in TP2 since. If there has, please let me know. You should ask David Barrett-Lennard that question. Cheers, Dan -- 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.
