The communication lower-bound conjecture for multi-value Byzantine agreement

Let $n$) nodes form a network with up to $t$ faulty nodes, and let $l$ be the length of the value on which agreement is required. If agreement throughput is $R$ bits per unit time, let the sum capacity denote the total network capacity in bits per unit time.

Communication lower-bound conjecture. In order to achieve agreement on $l$ bits, at least

$$\frac{n(n-1)}{n-t}l$$

bits need to be transmitted in the network. Consequently, achieving agreement throughput $R$ requires sum capacity at least

$$\frac{n(n-1)}{n-t}R$$

bits per unit time.

The conjecture would establish optimality, in average communication cost per agreed bit, of the algorithm presented in the paper. Its proposed argument reduces the claim to a further lower-bound conjecture about detecting disagreement among $k$ arbitrary $l$-bit initial values; the source does not establish that auxiliary claim.