[messaging] Partial ordering, dynamic groups and event ordering

[Ximin Luo]

On 12/03/14 20:42, Ximin Luo wrote:
> # Problem 2: defining consistent orders for global events
> 
> In the case of a total-ordering on messages, it is simple "when" a person joins the chat, since the history is linear, and all events are "before" or "after" any other event.
> 
> In the case of a general partial-order, where we can have arbitrarily-many branches, this problem is not solvable. A party may fork the chat and decide to completely ignore a decision-event. But - our restriction (c) forces a decision-event to be accepted, or else dissentors must stop participating.
> 
> However, the traditional total-ordering sense of "before" (a <= b) or "after" (b <= a) is no longer useful, since there may be events that are neither <= nor >= wrt a decision-event. Instead, we can talk about "not-after" and "after" a decision-event, and now the transition between "not-after" and "after" is a cut in the graph that might span multiple edges.
> 
> So far, things are still manageable. However, when we bring multiple join/part events into play, the question of "who is in the chat" becomes more complex. (This is vital, because you need to know "who do I send my next message to".) In our current model, join/part events are not totally-ordered, and picking an arbitrary order for these events to operate on "a set of participants" may lead to inconsistencies between participants. I have only fully-defined this problem in the past few days, so we'll see how hard it is to resolve, but we may need to introduce additional restrictions on top of (c) and (e).
> 
> Comments, advice, and/or pointers to any previous research in this area would be greatly appreciated!
> 

It looks like things will be consistent with no other changes. :)

It turns out that set operations do not have "edit conflicts", so we are OK with partially-ordered join/part events. Here's the proof:

For simplicity, we only allow single-parent messages to *change* the set of participants from the previous message. This can be verified by everyone else.

All multiple-parent messages b *must* have members (i.e. sender+recipients) = merge_mem(A), where A are the parents of b, and merge_mem is defined as follows:

def merge_mem(A):

    Let O be the least-common-ancestors of the A.

    If |O| = 0, then immediately return the union of mem(a_i) for all a_i in A. (We have not explicitly disallowed chats with multiple roots, and we can continue to support them *in principle* here.)
    If |O| = 1, let mem_o be mem(o), i.e. the set of members (sender + recipients) of the single message o in O.
    If |O| > 1, then let mem_o = merge_mem(O). (This is what happens in the default "recursive merge" algorithm in git.)

    Then, for each a_i in A, define:

    - add_i = mem(a_i) \ mem_o, the members joined in branch a_i, and
    - sub_i = mem_o \ mem(a_i), the members parted in branch a_i.

    We have, for all i, add_i is disjoint of mem_o, and sub_i is a subset of mem_o.
    Therefore, union(add_i) is also disjoint of mem_o, and union(sub_i) is also a subset of mem_o.
    Therefore, there is no conflict between +union(add_i) and \union(sub_i).

    So, return mem_o +union(add_i) \union(sub_i), which is equal to mem_o \union(sub_i) +union(add_i)

end merge_mem

Since we have an actual procedure for merge_mem, it is well-defined, and verifiable by everyone else. It also does the "intuitively-right" thing.

To calculate "the current set of participants" (i.e. which members we should send to next), we just calculate merge_mem(tips_of_all_known_forks), i.e. what mem(b) would be if we were to send b right now.

Actually, we do not even need the *must have members* requirement, since we can always calculate what changed between the actual mem(b), and what the "merge" should have resulted in. But the restriction will probably make {building more complex things on top of this} easier, so I will choose this route for now.

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/20140313/14932afc/attachment.sig>