[messaging] Merging partially-ordered membership operations was Re: Message order in group chat (attempt at summary)
trevp at trevp.net
Mon Apr 21 08:22:23 PDT 2014
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 ?
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
More information about the Messaging