[messaging] Matrix.org: Decentralized group chat

Jeff Burdges burdges at gmail.com
Wed Mar 11 11:59:27 PDT 2015

On 11 Mar 2015, at 14:55, Ximin Luo <infinity0 at pwned.gg> wrote:
> In summary: with merge algorithms that don't need to think about partial history, b and d .. **must** have the same view of the membership if they have seen the same partially-ordered history events


> 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 just saying it’ll depend on the application so here “solve” means "provide a reasonable set of primitives for application developers.”  If those primitives have unavoidable failure modes then one documents it and moves on. 

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

That would solve it, but that’s excessive since some merges are possible.  A fork is a new thread message that does not request automatic merging into another thread, but builds upon some past thread state. 

I’m proposing forks as one reasonable “primitive” operation upon which different applications could couple with other operations to impose different semantics. 

Just one possible approach : Allow forks as new threads with history pointers to other threads.  Allow add operations by anyone.  Allow leave operations, but not kick operations.  Allow ban request operations for non-members at thread creation time. 

We can produce exactly your scenarios with add and leave operations here, but the semantics is “damn that thread keeps sending me crap I need to leave again”, which might be automated, rather than “this obnoxious guy has a network of lag bots that makes it impossible for me to kick him” in the kick scenario. 

Also, bans are quite clumsy in that they expose contact information to future members, so they actually violates your anonymity desire that motivates this whole discussion, but you might just fork rather than fork+ban on the first attempt if that’s an issue. 

> 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 .. 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.

As I pointed out, “he goes or I go” aka "fork with ban plus leave” could provide d with a bd thread along with the option to join spurious thread like azc, etc, which I think is reasonable. 


More information about the Messaging mailing list