In short: I agree with Ximin; group messaging should be consistent. Ximin's proposal: a sequentially consistent log. This is likely to cause excessive message delays, as Trevor rightly worries about, even with a pure reorder channel.
-- Alternative: sequentially consistent, partially-ordered message trees. Causality == responding to a specific message: so just include the hash of the message you're responding to, per Ximin's proposal. Consensus on these trees is, in fact, possible. Lamport's Generalized Paxos paper describes how to do this for arbitrary posets. Relaxing total ordering to partial ordering speeds up time to consensus a lot.[paxos] Concerns about the precise client-server architecture are rather separate from the consensus algorithm design; anything targeting a mass audience will require a reliable, available server. (IRC-style chatrooms are not a mainstream UX.) -- UI proposal: Slashdot-comment-style message trees, but with, e.g., a spinner for messages not yet received.[2] (A warning would cause security fatigue.) Realizing a decent UX on a small mobile device is by far the trickiest part of this. [paxos]: http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#generalized [1] If you want to achieve weak temporal order, just hash together your current poset of messages using some (essentially arbitrary) canonical total-ordering. If you don't want temporal order, just hash the empty set. [2] iMessages sometimes shows a spinner for reordered/partially downloaded messages in the two-user case already. It works fine. _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
