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
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
