[messaging] Message order in group chat (attempt at summary)

[Trevor Perrin]

On Sat, Apr 19, 2014 at 9:16 AM, Ximin Luo <infinity0 at pwned.gg> wrote:
> On 19/04/14 16:45, Trevor Perrin wrote:
>> On Sat, Apr 19, 2014 at 6:53 AM, Ximin Luo <infinity0 at pwned.gg> wrote:
>>> On 19/04/14 00:54, Trevor Perrin wrote:
>>>>
>>>> To handle "join" and "part" events, I think we can assume these
>>>> actions are represented as messages which operate on the "member-set"
>>>> each participant recognizes.  The question Ximin has thought about
>>>> earlier is how to handle "merging" partially-ordered changes to the
>>>> member-set
>> [...]
>>>
>>> I have an algorithm (with source code and a few test cases) for this, plus a semi-formal argument on why it works, and also why it's the unique solution. It would be good to formalise it. It's probably a little too technical to post here but I can explain it in more detail next time we meet.
>>
>> Thinking more: if a group chat allows member-add but not
>> member-delete, then this is is easy, right?  The merged member-set is
>> just the union of the parent member-sets?
>>
>> With delete, there's not a perfect solution: what if one parent branch
>> adds Bob, and another adds Bob, then deletes him?  Since these
>> branches aren't ordered, I think it's ambiguous whether the merge
>> should contain Bob or not.
>>
>
> I'd argue the correct merge is that it should contain Bob. Perhaps I'm biased in my assessment, since this is what my algorithm does :p

OK.  So a "member-delete" message would cancel all causally-prior
"member-adds" of that member (though not necessarily all
temporally-prior ones).

Seems reasonable.  Does the below work? -

Clients track sent/received messages, but garbage-collect messages
more than X seconds older than the latest message (i.e. messages are
garbage-collected once they are old enough that new messages are
expected to refer to later ones).

For each message, clients track:
 - a member-set M, each member associated with the messageID(s) that added it
 - a deleted-member-set D, each member associated with the
causally-prior messageID(s) that added the member being deleted

The client's view of the current M and D is derived by merging M and D
from its immediate predecessor messages:
 - M = union(M from predecessors), D = union(D from predecessors)
 - if there is a member listed in M and D, delete from the member in M
all the messageIDs listed for the member in D.  Then, if the member
has no messageIDs in M left, delete the member from M.

When messages are garbage-collected, if the last mention of a
messageID for a member in M is removed, then the same messageID can be
removed for that member in all D.  (In other words: once a member-add
has been fully cancelled by a member-delete in all messages that a new
message could refer to, the member-delete no longer needs to be
tracked.)

---

This is getting complicated, would be great if someone could create a
wiki or something and try to list:
 - threats we're defending against
 - various assumptions that can be made about the underlying network,
group semantics, and UI
 - algorithms and their options


Trevor