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

[Ximin Luo]

On 29/04/14 09:15, Michael Rogers wrote:
> On 27/04/14 18:45, Ben Laurie wrote:
>> If it is delayed for all recipients, then causality cannot be
>> violated :-)
> 
>> Here's a crazy idea.
> 
>> Each client maintains a list of messages it knows each other
>> client has seen (because that client has told it so). Every time it
>> sends a message to another client, it also sends all messages it
>> has seen that it does not know the other client has seen. It also
>> sends a list of messages it knows the other client doesn't know it
>> has seen.
> 
> In a word, Usenet. This has the nice property that if a subset of the
> members are connected to each other but disconnected from the other
> members, they can carry on the conversation and see each other's
> messages, without having to wait for the other members.
> 
> However, it definitely requires a threaded rather than linear UI.
> 

A threaded UI is only necessary if you implement "in-reply-to" pointers, since this generates a tree structure. By contrast, "latest-messages-seen" pointers generate a DAG structure, and *are able* to model a linear chat system.  But the algorithm Ben mentioned (auto-re-sending older messages not yet acknowledged by others) can be implemented for both structures.

I agree that trees of threads are "simpler" to think about, than DAGs and merge algorithms, but they have several downsides. The concurrency in a tree is pointless, because one is never able to see the merged effects of any concurrency - you only see a linear history and ignore other forks. In a DAG however, each message automatically merges all seen forks, and the concurrency here is actually visible.

For example, if you have a transcript consistency verification, you generally need n messages (one from everyone) to confirm this. With a tree structure, you would need to do this in every single branch. With a DAG structure, you can do this for all branches at once, using a merge algorithm. Similarly with a ratcheting mechanism, you would need to duplicate the ratcheting state across all branches in a tree. (One can think of forward secrecy ratchets as an optimisation problem of fitting the DAG dependency graph of your KEX protocol into the actual DAG of the conversation.)

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/20140429/8f94670a/attachment.sig>