[messaging] Matrix.org: Decentralized group chat

[Matthew Hodgson]

On Mon, 9 Mar 2015, Trevor Perrin wrote:

> On Sat, Mar 7, 2015 at 4:13 PM, Ximin Luo <infinity0 at pwned.gg> wrote:
> >
> > For a private dynamic group chat, the merging requirements are not 
> > exactly the same as in a collaborative environment like Google Wave:
> >
> > - for a basic application, one does not *need* to merge arbitrary 
> > state. The only thing you need to merge is an unordered set (the 
> > membership set).
> 
> 
> Yeah, I agree that merging in group messaging is simpler than the
> "merging of edited documents" in revision-control and
> collaborative-editing [1].

FWIW we've deliberately descoped OTs from Matrix so far.  If someone wants 
to go down that rabbit hole, patches welcome ;)

> It's true that group members might simultaneously send messages or 
> change group "fields" (add/remove user, change group name).  There might 
> also be connectivity problems / delays between group members. You could 
> view these as edits to the group state in different branches, which have 
> to be "merged" by recipients into a consistent view of (message history, 
> membership, group name).

This is pretty much precisely how Matrix works.  The graph of events in a 
room is split into those which purely describe timeline information (e.g. 
instant messages, VoIP setup, arbitrary IoT data), and those with update 
state (e.g. room name, topic, membership, and indeed arbitrary key/value 
state).

> But this is simpler than merging source code:
> 
>  (a) Text messages from users don't have to be edited together, they
> just have to be displayed.  You could display the causal order in some
> way, or display messages in arrival order.

Precisely.  Currently clients display new messages in arrival order, and 
otherwise rely on their server to linearise the DAG when replaying 
history.  If extensible messages imply application-domain causality (e.g. 
a VoIP session answer being dependent on a VoIP session offer), then it's 
up to the client to buffer up processing the events until the dependent 
one arrives.

In the work-in-progress v2 client-server API we also give clients the 
option of receiving the DAG pointers so they provide a fun sidebar UI to 
handle conversation forks/netsplits etc, or put UI in for placeholder 
missing events until they arrive in the 'right' DAG order.

>  (b) For any group fields that can only be changed by a single admin,
> merging isn't necessary, since causal order will indicate the latest
> value.
> 
>  (c) If group membership can be added but not deleted, then merging is
> easy (union of group members).

As per elsewhere in the thread, this is the hack we're using for now.  You 
can check in any time you like, but you can never leave (other than 
setting your membership state key to 'leave' ;)

> There are cases where these aren't sufficient, e.g. if group
> membership could be added+deleted by multiple parties.  Ximin touched
> on that, and it's worth discussing more.  But even that has fairly
> specific features (e.g. unordered set), so makes me skeptical of the
> need for general-purpose merge algorithms.

Indeed, so far we have survived without them.  I suspect our next step 
should be to formally write up the algorithm (as opposed to draft notes) 
and post it here for proper review.  I am sure we have some holes here 
(and certainly risks in the heuristic side of distinguishing netsplits 
from malicious attacks, etc).

M

-- 
Matthew Hodgson
matrix.org