[messaging] Matrix.org: Decentralized group chat

[Jeff Burdges]

On 10 Mar 2015, at 17:08, Ximin Luo <infinity0 at pwned.gg> wrote:
> Merge the unordered set of members. 
> 
> In the following diagrams, the node labels (e.g. "bd") represent the set of members ("b", "d") at a given message/node/event. Someone wants to merge the blue nodes, which are the same message in both diagrams. Black edges are 1-parent messages, grey edges represent merge messages that don't include a further membership operation. (If it is unrealistic to imagine membership operations taking only one event to complete, then instead imagine extra messages in between the nodes.)
> 
> From b's point of view, they have full visibility of the history, and can execute the merge as normal:
> 
> https://people.torproject.org/~infinity0/res/mcrypt/partial-vis-1.png [1]
> 
> But when d executes the merge, they have an incomplete view of history, giving a different result:
> 
> https://people.torproject.org/~infinity0/res/mcrypt/partial-vis-0.png [0]
> 
> The problem is to resolve this difference, somehow. I suspect it's impossible in the general case; the "solution" I had been playing with is (roughly) to detect "impossible" conditions and wait until it is possible.
> 
> I agree with the rest of what you said, and have implemented it in a prototype.


You’re aren’t *only* merging an unordered set of members though, even if the issue is visible at that level, because you’ve some ambient application that imposes some semantics on the merge operations.  


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.  

Said differently, what do your grey arrows from the blue nodes to the bd grey node mean?  You didn’t label them like you labeled the black arrow between grey nodes.


If we interpret your diagrams as connectivity difficulties rather than intentional privacy operations then we observe that b should be happy with whatever merges can be accomplished.  I’ll therefore interpret all the +/- arrows an intentional operations by the users. 


A priori, I’d expect b added d to both the ab and bc conversations to make the blue nodes, as b adding a and c to the bd conversation has a different semantics, so..  

Those arrows could hypothesize that d’s client mysteriously detected the common history back to b’s first message to merge these separate branches.  How?  Why?  Isn’t that already a violation of users not seeing previous history?  I guess this isn’t the situation. 

Yeah, if b set a unique thread id way back in the beginning, then obviously d’s client might merge the two threads in that way, but that’s loony since b already split the thread.  And such a thread id dictates that d’s merge is correct anyways. 


Instead, those blue nodes with two parents must represent b executing conscious merge operations, yes?  

We might for-example have a private shared git-like system where the blue nodes represent two new branches along with an assertion that they should both supersede the bd grey branch.  In this case, the green node represents another conscious merge operation by d, which screws up b because b failed to warn d to keep the branches separate.  Meh, not surprising.  Op sec is hard. 

We should not imho worry about anonymizing distributed version control like this.  If an application like git benefits significantly from shared history then share the required history, including the user’s social graph when necessary.  Any users who require more privacy can pass through snapshots or even use diff & patch manually. 

Jeff