[messaging] Message order in group chat (attempt at summary)
trevp at trevp.net
Sun Apr 20 11:33:00 PDT 2014
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
>>> 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
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
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
More information about the Messaging