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

[Trevor Perrin]

On Sun, Apr 20, 2014 at 5:20 PM, Ximin Luo <infinity0 at pwned.gg> wrote:
>
> I'm unsure what you're trying to achieve with M, D.

I'd like to understand the algorithms for tracking causal order and
group membership.

There's different membership policies, depending on who can add
members (anyone? group leader?) and who can delete (anyone? group
leader? you can delete yourself?).  But I think the "anyone can add
and delete" policy is the most complex, so if we can handle that we're
in good shape.

I think my algorithm works.  Yours probably works too, though I'd like
to see a fuller writeup.


> Come to think of it, I think you will actually never get *any* items in D. If an entry (mId, member) is in D for a message, then it must also be in M, since mId is causally before that message.

No, I meant the following:
 - A "member-add" message would result in (mId, member) being added to
that message's M.
 - A "member-delete" message would move all entries associated with
member from M to D.


> But then, you ought to delete this entry from both D and M.

The only case where an entry in D could be removed (or ignored) was
once it becomes irrelevant (all references to mId in any message's M
have been garbage-collected).


> If the LCA is multiple sets, you recursively merge these first - this is what git means when it says "merge by recursive". If you merge multiple parents, you fold over the pairwise merge - this is what "git merge-base" does.

Do you mean something like this?

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

That looks complicated.  Maybe you should try to write out the
pseudocode for all this, so we can evaluate.


Trevor