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

Michael Rogers michael at briarproject.org
Wed Apr 30 23:45:39 PDT 2014

Hash: SHA256

On 30/04/14 23:58, Ximin Luo wrote:
> 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".

That's why I said for linear conversations, which are totally ordered
if simultaneous speaking isn't possible (or
not-totally-ordered-but-more-restricted-than-a-general-DAG if it is).

> 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.

I'm using partition to mean a loss of full network connectivity
between the members.

The question I'm interested in is whether connected members can
continue to get partial use out of the system during a partition by
carrying on a local conversation among themselves. For a system that
tries to establish a linear transcript, I don't think it makes sense
to allow that even if the protocol makes it possible (as Ben's
protocol would, for example). But for systems that try to establish
less strictly ordered transcripts, such as thread trees, it may make
sense to allow it.

Version: GnuPG v1.4.12 (GNU/Linux)


More information about the Messaging mailing list