On Sat, Apr 19, 2014 at 9:16 AM, Ximin Luo <[email protected]> wrote: > On 19/04/14 16:45, Trevor Perrin wrote: >> On Sat, Apr 19, 2014 at 6:53 AM, Ximin Luo <[email protected]> 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 _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
