The lower bound

Theorem 12594

Consensus with P needs f<n/2.

Proof. Suppose that there exists such a protocol, and that n is even. We divide the set of processors into two sets, P₁ and P₂, consisting of n/2 processors each.

Now, we simulate the protocol when all processors are given input , all detectors works perfectly, i.e., without any error, and the processors in P₂ are crashed as soon as they start their execution. After some finite time t₁, all processors in P₁ must decide on , by non-triviality and limited bureaucracy.

Next, we simulate the protocol when all processors in P₁ are given input , all processors in P₂ are given input 1, all detectors works perfectly, and the processors in P₁ are crashed as soon as they start their execution. After some finite time t₂, all processors in P₂ must decide on 1, again by non-triviality and limited bureaucracy.

Finally, we simulate the protocol when all processors in P₁ are given input , all processors in P₂ are given input 1, no processors are crashed, but the detectors make errors until time $\max(t_1,t_2)$. Then, all processors in P₁ will execute as in the first simulation, and all processors in P₂ will execute as in the second simulation, which implies that all processors in P₁ will decide on  and all processors in P₂ will decide on 1. This violates agreement, which contradicts our initial assumption.$\Box$