[messaging] Group messaging consistency under resource constraints

[David Leon Gil]

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.