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