[messaging] Matrix.org: Decentralized group chat

[Ximin Luo]

On 11/03/15 01:14, Jeff Burdges wrote:
> 
> On 10 Mar 2015, at 23:02, Ximin Luo <infinity0 at pwned.gg> wrote:
>> On 10/03/15 19:36, Jeff Burdges wrote:
>>> There are three separate conversations from b’s perspective before the blue nodes, and a, c, and d only know about the ones they’re involved in, so some action by b precipitated the merges that occur in the blue nodes.  
>> No, it's the same conversation. Different membership were initiated by different people at different times. (Possibly I didn't explicitly define enough members to be able do these concurrent operations, but you can just imagine an extra constant set of members "xyz" at each node doing these operations, which are the black edges labelled +a etc.)
> 
> Ahh yes!  We could split b into x, y, and z who’re holding a conversation together and hold different opinions about a,c, and d, respectively, so d is unaware of the dislike x and y hold for c and a, respectively.  If d were not present then you’d want ab and bc to merge into b probably.  If d is present then network delay between x and y allows d to perform a different merge.  Nice  :)
> 
> Imagine now that a and c left voluntarily, as opposed to being kicked.  In this case, all b stop messaging them, but d continues.  I donno if that’s too bad, well email causes this problem way more easily.  If a and c recognized the thread they could leave it again, maybe automatically, but even manually works. 
> 

Hmm, I don't understand some of the terminology you used. What do you mean by "opinion"? The desire to kick, or the refusal to recognise their participation in the session, or what?

But I *think* you "get" the diagram. How I would describe what I *think* you meant, is:

- suppose b is actually xyz.
- x has as their "latest messages" the nodes "ab" and "bd" (i.e. they saw +ac, -c, +d), they merge these nodes which results in the *left* blue node
- y has as their "latest messages" the nodes "bc" and "bd" (i.e. they saw +ac, -a, +d), they merge these nodes which results in the *right* blue node
- then z sees both blue nodes (and all their ancestors), and wants to merge the green one
- d sees a bunch of other stuff, I'm too lazy to write this explicitly but hopefully the reader can infer it

The thing is, d does not *necessarily* need to continue messaging a or c. I would like to figure out a merge algorithm, such that d (and anyone else that sees the blue nodes, but not some of their ancestors) would do exactly the same thing as b. Or, if this is impossible, then some other mechanism whereby d (doesn't have to do / is prevented from doing) something that's inconsistent with what b would do.

(BTW, the kick/voluntary thing is not relevant - either can be described as an event where the membership changes)

In summary: with merge algorithms that don't need to think about partial history, b and d (and anyone else) **must** have the same view of the membership if they have seen the same partially-ordered history events, or equivalently (because we're delivering messages in causal order) the same set of "latest messages". However, it is intuitive that this invariant should hold even if different people see different subsets of the history, as long as they share the same "latest messages", and this is the problem that I'd like to solve for partially-ordered private group chat.

> I’m therefore wondering if the kick operation should be considered unnatural in the secure group chat context.  Just focus on forking discussions instead. 
> 

What do you mean by forking? Yes, if inverse operations ("kicking") don't exist then we avoid this problem. But note that if you disallow kicking, then you disallow leaving - in terms of operations on membership sets, they are the same operation. Of course someone can just disconnect from the transport, but the system would force remaining members to keep on encrypting to them. This seems very ugly.

Also removing kicking as a feature seems to me like giving up too easily. There is not yet an "impossibility theorem" about this, so I'll keep trying. :p

>> One observation is that d mis-infers some merge edges to be "membership operation" edges, because some other parents (of the blue nodes) are not visible. Maybe this fact could help to work towards a solution.
> 
> I donno if simple thread ban records would suffice since d could miss a whole kick war while offline.  You could probably impose an ownership hierarchy that re-propagated it’s authoritative view, but that offends my anarchist sensibilities by creating property, and sounds odiously complex. 
> 

I have not thought things through that far, but two comments:

- the concept of "offline" is at a separate layer. If d misses messages whilst offline, then he will send messages pointing to an older branch. Once he receives the missed messages, the merge algorithm (once we figure that out) will define precisely what is to be done.
- in my model, I do not yet have a concept of the "subject" of an operation. Perhaps this is not a necessary concept - by accepting an operation and building on top of it, everyone implicitly agrees to that operation. Otherwise, you reject the operation by not responding to it (and leaving the session). When everyone agrees to an operation, the idea of the "subject" of it is not strictly necessary. But perhaps this is actually a flaw. I don't know yet. Yes, I have not thought about access controls on membership operations: currently anyone can kick/invite anyone else - but anyone can re-invite a previously-kicked member too.

> 
> We should seriously consider resolving this by abandoning the kick operation in favor of forking.  Implement "kick” with the semantics of “ignore user” or “he goes or I go” aka “fork & drop original”.  And client software should respect user bans established at thread creation time. 
> 
> I’ll reinterpret your scenario in this context : 
> - x forks abc to ab dropping c, sending y an invite to the ab thread, and maybe dropping the abc to ayzc.  
> - y forks abc to bc dropping a, sending x an invite to the bc thread, and maybe dropping the abc to axzc.  
> Now x and y must both consider if they wish to remain with each other or a and b, respectively.  If either x or y choose bc or ab, respectively, then they could refork down to a b thread. 
> 
> Also, ayzc and axzc both still contain conflicting pairs, so depending upon the “fork & drop original” operations semantics, we might wind up with only azc.
> 
> Initially d was only invited to chat with b, but presumably that invite propagates into the forks since d was not banned, so d winds up with invites to ab and bc, and eventually the final b thread, along with ayzc and axzc.  And d might retain an invite to message just the original b thread all along.  All this sounds confusingly like email for d though since she doesn’t know what’s going on. 
> 
> In this case, there is at least a semantic reason for keeping the thread ban records around permanently, so d could learn those, which might help her client default to b over ayzc or axzc.  Also, if those two made it to azc then d might face an interesting choice, but ideally he can treat it as a mostly separate conversation, like in email.  
> 

What do you mean by "fork"? Do you mean that we never attempt any merges?

X

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git