[messaging] Merging partially-ordered membership operations was Re: Message order in group chat (attempt at summary)

[Ximin Luo]

On 21/04/14 16:22, Trevor Perrin wrote:
> On Mon, Apr 21, 2014 at 6:24 AM, Ximin Luo <infinity0 at pwned.gg> wrote:
> Suppose a simpler policy:  a member-delete message takes priority over
> member-add even if they're siblings.  Since siblings only arise in the
> "simultaneous send" case, where it's sort of ambiguous what's going to
> happen anyways, I argue this policy is reasonable.
> 
> In this case, clients can track M and D member-sets, but don't have to
> associate members with the messageIDs that added the member.
> 
> A member-add message adds a new member to M, and removes that member
> from D (if present).
> 
> A member-delete message adds a new member to D, and removes that
> member from M (if present).
> 
> A merge sets D=union(D from predecessors), M = union(M from predecessors) - D
> 

To bring everyone else up-to-date (Trevor and I talked about this already): the problem with this approach is that, if a delete happens, then the conversation forks, one would need to re-add someone on every single branch, in order for a merge to work successfully later.

An alternative, is to tweak the id-tracking version a few posts prior to this (which I think does actually work, but still has the "redundant info" problem), but use sequence numbers instead of ids. This doesn't "work perfectly" but might be "good enough", but this is up for debate.

One nice thing about the DAG-merge algorithm I specified before, is that it generalises *to any sort of state* you need to merge in the DAG, not just member-sets - as long as you can write a (non-conflicting) 3-way-merge algorithm for your state. The DAG-merge algorithm uses the 3-way-merge as a primitive for applying state-diffs, and the rest of it works independently of the state, using only the DAG structural information to do its job.

So, if one wanted to store more complex state than "member-sets", one only needs to write a 3-way-merge algorithm, rather than doing one for DAGs all from scratch.

(Indeed, what I wrote before is exactly what git does, except the 3-way-merge primitive is over unordered sets, rather than line-by-line files, for which a non-conflicting algorithm doesn't exist).

X

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 880 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140429/1cf58e51/attachment.sig>