[messaging] Merging in partially-ordered private group chats; was: Re: Matrix.org: Decentralized group chat

[Ximin Luo]

(should have re-titled the thread a while ago)

On 11/03/15 19:59, Jeff Burdges wrote:
> 
> 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
> 
> Yes.
> 
>> 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. 
> 

OK, I think I understand what you mean. But these "forks" are a different *type* of thing from branches in the partial order.

With partial ordering, branches happen when two people to do things at the same time, without seeing each others' actions. This is a fundamental part of being in a distributed system (without resorting to a "consensus" accept/reject mechanism) - it is outside of users' control, and it will happen often or less often depending on how asynchronous the transport is. Further, we can enforce the semantics that "events sent by the same author" should be in a *total order*, which naturally restricts how branched the partial order may be. In terms of the application semantics, we try to keep the message history as a "single thread of meaning" (for lack of a better term), and the merge algorithm is a vital part of keeping this unified session identity.

With forks, this is an intentional human operation about the *semantics* of the messaging thread. Here, we would not want to enforce the per-author-total-ordering semantics, since people should be able to follow and reply to as many forks as they wish. Importantly, if two people happen to concurrently reply to the same thread *without wanting to fork it*, this would still be a branch in the partial order (unless you use a consensus mechanism). So, I think "thread forks", if you want to add that as a feature, are best done as an additional representation (i.e. different types of "parent pointers") outside of the partial order for messages.

X

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