[messaging] Partial order group chat with partial history visibility

[Ximin Luo]

Jeff Burdges:
> 
> In other words, there is no globally consistent view, but if the event
> membership data U[v] was magically globally consistent, then the general
> merge algorithm can be pairwise consistent by running it again only
> messages known to both parties. 
>

The data U[v] is embedded into each message/event: it's globally consistent by definition, not "magically" :p. Further, anyone that can read/decrypt v (i.e. they are in U[v]) can also read U[v] - i.e. you know the other members of that message/event.
 
> I donno if that's surprising by itself, but the tricky part appears to
> be that the merge algorithm is running with awareness of the graphs of
> each party, which do differ.
> 

Right, this difference is what makes it surprising. One can construct other examples where U[v] are the same, but if you arbitrarily change the edges (the parent references) the results differ (and correctly so).

For example:

    0           0
   / \         / \
  1   2  vs   1   2
 /   /       / \ /
3   4       3   4

Merge(3, 4) is different for these cases, if U[1] != U[0]. But these sorts of transforms are ruled out if the second one is meant to be a "partial" view of the first one.

> What is this merge algorithm?  It's not still just talking about
> membership, right?  
> 

It's a merge algorithm acting on U[v], which are unordered sets. (As another example: in DVCSs each event v is associated with a directory tree T[v], which git treats as trees of line-by-line files.)

> 
> Is there even a global partial order G for typical DVCs for example?
> It's just the local ones that actually exist on disk, right?  
> 

Yes, that is G the "full history".

> There are mappings of patches between these local partial orders, but I
> think patches represent different arrows in different local ones.
> 

"Patch" is a secondary concept that's useful in some contexts, but we can ignore it here, and talking about patches confuses the discussion IMO. We only talk about "edges", i.e. parent references. You can construct a patch out of this by calculating diff(e.src, e.dst), but you don't need to do this for every single edge, and the standard Merge algorithm doesn't do this.

X

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git