Reconcile differences between threshold calculation here and in paper.

[rphmeier]

The paper uses (n+f+1)/2 and we use n-f -- for small authority sets this is
a tradeoff in safety and liveness.

cc @AlistairStewart

[romanb]

Could you elaborate on the tradeoff between safety and liveness? I mean, for n < 4 where f = 0, we have

n = 1 ==> threshold >= (n + f + 1) / 2 = (1 + 0 + 1) / 2 = 1
n = 2 ==> threshold >= (n + f + 1) / 2 = (2 + 0 + 1) / 2 = 3/2 (so threshold >= 2)
n = 3 ==> threshold >= (n + f + 1) / 2 = (3 + 0 + 1) / 2 = 2

and for n > 3 where f >= 1, we have

n >= 3f + 1 ==> (n + f + 1) / 2 >= (4f + 2) / 2 = 2f + 1

so >= (n + f + 1) / 2 is always a safe threshold for a supermajority, isn't it? Using n - f seems to unnecessarily require one more vote for a supermajority than necessary whenever n is a multiple of 3.

[rphmeier]

n = 3 ==> threshold >= (n + f + 1) / 2 = (3 + 0 + 1) / 2 = 2

Well, you're probably right, but I don't think it makes much difference in practice. If you get that 1 extra misbehaving validator, n - f keeps you safe but not live (as they can withhold and prevent quorum).

Liveness failures in GRANDPA are easier to recover from than safety failures. We could make this configurable, for those who'd like to make a different trade-off.

[romanb]

I see, thanks. So to summarise: Both n - f and (n + f + 1) / 2 can tolerate (w.r.t. both safety and liveness) the same number of byzantine faults for any n, but whenever n is a multiple of 3, n - f makes a preference for safety in the face of one more byzantine fault at the cost of liveness if the fault is indeed non-byzantine (e.g. crash fault) whereas (n + f + 1) / 2 makes a preference for liveness as it can tolerate one more non-byzantine fault (e.g. with n = 3 it can make progress with supermajority 2, at n = 6 with supermajority 4 etc).

I'm not sure that distinction is really worth deviating from the paper, mainly because any deviation that is not very prominently documented is a potential cause of confusion for anyone reviewing the code, but if n - f is supposed to stay in the implementation, then obviously the only option for reconciliation (and addressing this issue) is to change the paper.