> > 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. >
I've been working on implementing branching and merging using the wave OT code. My code passes a fairly simplistic test but I need to do more testing to see if there are any limitations. While working on that code I gained a better understanding of OT and the present intention preservation problem. And, while I see your point, I'm still not sure yet how much of a problem it is. I also see one possible solution. When deleting a range of characters, leave a marker in their place. When other operations are transformed against that delete, the marker would remain and allow the preservation of intended order. This would, however, lead to a proliferation of markers, so I'm not sure yet if adjacent markers could be merged or if they would need to remain. I need to read Abdessamad's paper in more detail to try and understand how he solved it. -Tad -- 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.
