On Wed, Mar 3, 2010 at 9:50 PM, Daniel Paull <[email protected]> wrote:
> > .... > Let's emulate the TP2 puzzle that I noted in an earlier message, but > this time using branches rather than clients generate concurrent > operations. Let's start with a document whose state is "X" and create > three branches and generate one operation on each branch (note that > the common prefix is empty, so we can drop it from the above equations > for the sake of simplicity). > > B1 = [O1] O1 deletes the "X" > B2 = [O2] O2 inserts "A" before the "X" > B3 = [O3] O3 inserts "B" after the "X" > > If we wanted to merge all three branches together, then we need to > perform two pair-wise merges. For example, merge B1 onto B2 to form a > new branch (which we will call B4) and then merge B3 onto B4: > > B4 = merge( B1, B2 ) = [ O2, O1' ] > B5 = merge( B3, B4 ) = [ O2, O1', O3' ] > > B5 is the final merged result. More concisely, we can write this as: > > merge( B3, merge( B1, B2 ) ) = [ O2, O1', O3' ] > > There are 6 possible pair-wise merges that can be done in order to > merge all three branches together. .... Aren't there 12 possibilities if we assume merge(X,Y) != merge(Y,X)? (6 choices for which ordered pair to merge first, times 2 choices for the order of the final merge. Or to see it another way, 6 choices for the order of the operations within the expression, and 2 choices for how to parenthesize the expression, i.e. (x (y z)) vs. ((x y) z).) (Whereas if we assume merge(X,Y) == merge(Y,X) then there are only 3 possibilities.) - Bruce Smith -- 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.
