<div dir="ltr"><div>I don't think we disagree on 'buffering'; my point is that it can be made a (usually totally invisible) part of the UI.</div><div><br></div><div>[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.]</div><div><br></div>On Thursday, October 16, 2014, Ximin Luo <<a href="mailto:infinity0@pwned.gg" target="_blank">infinity0@pwned.gg</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 12/10/14 04:57, David Leon Gil wrote:<br>
> Consensus on these trees is, in fact, possible. Lamport's Generalized<br>
> Paxos paper describes how to do this for arbitrary posets. Relaxing<br>
> total ordering to partial ordering speeds up time to consensus a<br>
> lot.[paxos]<br>
><br>
<br>
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.<br></blockquote><div><br></div>So, we have to separate two concerns: One is whether the parties reach consensus at all. The other is whether they reach correct consensus.<div><br></div><div>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:</div><div>- the network is not partitioned;</div><div>- and there are no Byzantine failures.<br><div><br></div><div>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.</div><div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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.)<br></blockquote><div><br></div>(Another bit of terminology confusion: what database people call "consistency" implies "consensus" for a distributed database.)</div><div><br></div><div>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.)</div></div><div><br></div><div>[This was sitting in my drafts folder for quite a while.]</div>
</div>