[messaging] Message order in group chat (attempt at summary)

[Ximin Luo]

On 30/04/14 22:59, Michael Rogers wrote:
> I have a hunch that for linear conversations, something like the CAP
> theorem holds: if there's a partition, either the conversation has to
> pause or you have to give up consistency. Threaded conversations can
> be partition tolerant because they can sacrifice global availability
> and global consistency - branches of the conversation can continue
> with only local availability and local consistency, and if necessary
> global consistency can be reestablished later.
> 

The CAP theorem does not apply here - with partial ordering we are already sacrificing (global) consistency for a weaker form of consistency, anyway. I don't know what to call it, but it's stronger than "eventual consistency".

My exploration into merge algorithms is giving a better understanding of the cases where this may or may not be achievable. In causal ordering, one has a few further constraints on top of a general DAG structure:

- for any given user, their events are totally-ordered
- for any given user, if they refer to parents P in one event E, their future event E' >= E must refer to parents P' all of whose elements are >= all elements of P. Or equivalently, ancestors(E) is a subset of ancestors(E').

(Perhaps I should start preferring the term "causal order" rather than "partial order", to make this more obvious.)

This means that many possible sources of merge conflicts don't exist. For example, one single user cannot participate in multiple branches. So, if the global state is partitioned by "initiating user", this might enable a 3-way merge algorithm. This might be of relevance for representing policy-enforced join/part operations.

As a side note, I think you are using "partition" in two separate senses. The P in CAP refers to unintended loss of availability. This would be trivially detectable by a transcript consistency algorithm - from the POV of any partition, the users inside wouldn't receive acknowledgements from the users outside, and will know that something is wrong, and try to re-send.

OTOH, when you describe subsets of the original participants going off to talk about their own things "in a separate thread", this would be a partition of member-sets, which is something above and beyond a simple loss of availability. For starters, it would be intentional, not an error condition.

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/20140430/26deb1d2/attachment.sig>