LibraBFT latency analysis

Why the latency upper bound is 24∆ ? Can anybody explain in detail the derivation process? Thanks in advance.

Thanks for asking the question, the sentence certainly is confusing. We’ll take a look and get back to you on this.

1 Like

Thanks both for looking into this.

Property 3 gives a conservative latency bound for synchronous settings. It may be tightened.

The calculation proceeds as follows.

Property 2 says that every two honest validators enter a round r whose leader is correct within 2∆ of one another. The reason is that the first validator to ever collect a TC forwards it to the leader; the leader broadcasts it to everyone; hence, a total of at most 2∆ elapse.

Say that at time t0 the first honest validator enters round r. At t0 + 2∆, all honest validators will have entered round r, including the leaders of round r, r+1, r+2, and r+3. No honest validator will time out before 4∆ elapse in round r, hence they all receive and vote on the leader proposal in round r by t1=t0+2∆+2∆. Likewise, all honest validators receive and vote on the leader proposal in round r+1, r+2 within t2=t1+2∆, t3=t2+2∆, resp… Finally, they receive the leader proposal in round r+3 within t3+∆ and commit r. I am counting a total of t0+9∆.

We also don’t need 81 rounds in expectation to get 4 honest leaders in succession (we need less). but that’s another over-estimate.

The expected number of rounds to get a succession of 4 honest leaders, assuming 2/3 are honest and leader rotation is randomized, is roughly 13. See coin-toss analysis