[messaging] Merging partially-ordered membership operations was Re: Message order in group chat (attempt at summary)

[Trevor Perrin]

On Mon, Apr 21, 2014 at 6:24 AM, Ximin Luo <infinity0 at pwned.gg> wrote:
>
> I think this does work, but I see a few issues. It leaks some information about previous members in the session - I don't think the garbage-collection would be enough to hide this.

Wouldn't you need to send new joiners some history in both approaches?
 (Either they need M and D, or they need enough of the graph to
compute your "latest common ancestors").


> Here is the pseudocode with type annotations, but it will take me a lot longer to write up the justification:

I have trouble following this.  I guess you're doing some "recursive
merge" thing and constructing "virtual ancestors" per [1]?

I'm worried about how complex our algorithms are getting.

Suppose a simpler policy:  a member-delete message takes priority over
member-add even if they're siblings.  Since siblings only arise in the
"simultaneous send" case, where it's sort of ambiguous what's going to
happen anyways, I argue this policy is reasonable.

In this case, clients can track M and D member-sets, but don't have to
associate members with the messageIDs that added the member.

A member-add message adds a new member to M, and removes that member
from D (if present).

A member-delete message adds a new member to D, and removes that
member from M (if present).

A merge sets D=union(D from predecessors), M = union(M from predecessors) - D

?

Trevor


[1] http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html