[messaging] Matrix.org: Decentralized group chat

[Joseph Gentle]

On Tue, Mar 10, 2015 at 12:57 PM, Trevor Perrin <trevp at trevp.net> 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].
>
> 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).  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.
>
>  (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).
>
> 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.
>
> Trevor
>
> [1] http://en.wikipedia.org/wiki/Operational_transformation


Well, it depends what your use case is. If you just want group
messaging, that should be fine. (Hi! I worked on Google Wave back in
the day, helped opensource it at google and reimplemented a lot of the
tech in ShareJS.)

Wave's federation protocol was super complicated because the algorithm
we used required a unique global ordering of all messages. Newer
algorithms (like CRDTs) don't need that. They just need a partial
order kind of like a git's commit log. Each commit (or message)
specifies the head(s) of the tree from that client's perspective. But
this only matters for collaborative data editing - as Trevor said, if
you just want to do federated messaging, clients can just pick a local
order for messages and (I think) it shouldn't matter much if two users
see slightly different histories.

-J