On Tue, Mar 10, 2015 at 12:57 PM, Trevor Perrin <[email protected]> wrote: > On Sat, Mar 7, 2015 at 4:13 PM, Ximin Luo <[email protected]> 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 _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
