[messaging] Group messaging consistency under resource constraints

[David Leon Gil]

I don't think we disagree on 'buffering'; my point is that it can be made a
(usually totally invisible) part of the UI.

[ETA: Trevor's suggestion of "warnings" seems like it would lead to
security fatigue very quickly; I'd prefer to reserve warnings for really
exceptional circumstances, as in the kick conditions mentioned below.]

On Thursday, October 16, 2014, Ximin Luo <infinity0 at pwned.gg> wrote:

> On 12/10/14 04:57, David Leon Gil wrote:
> > 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]
> >
>
> It's possible, but with a probability that is low compared to
> cryptographic standards (like 99.9999%?). For transcript consistency
> purposes, I'm advocating to forget about the consensus / "common knowledge"
> problem, and focus on first-order knowledge instead.
>

So, we have to separate two concerns: One is whether the parties reach
consensus at all. The other is whether they reach correct consensus.

Probabilistic Paxos only ensures consensus in expectation. (Very rapidly.)
You can, however, determinize Paxos (this is usually done in
implementations); in this case, it always ensures consensus, provided that:
- the network is not partitioned;
- and there are no Byzantine failures.

W.r.t. the latter: Does it make sense to even *tolerate* Byzantine
failures? I.e., rather than just stopping participation in the session? It
doesn't seem like a service to users to let them continue in a conversation
in which either (1) one of the participants is forging messages/history or
(2) claiming that another participant is.


> In our case, P (for a message m) is "message m exists and is part of the
> session". (The original mpOTR paper also uses ["I know "P"] but calls it
> "consensus", which I'd like to correct before it gets too popular.)
>

(Another bit of terminology confusion: what database people call
"consistency" implies "consensus" for a distributed database.)

I think, however, that if, in your proposal, all users receive
all sent messages, you will necessarily reach consensus about the history
right before the next time increment. (And as best I can tell, if not all
users receive all sent messages, eventually no one will receive any
messages.)

[This was sitting in my drafts folder for quite a while.]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141020/077e2f27/attachment.html>