4. Examine the phase-king algorithm for consensus in the face of Byzantine failures, as given in Figure 14.11. This algorithm works when n > 4f. Presumably, the algorithm will fail for 4f ≥ n > 3f, even though this condition is a sufficient condition for the existence of a solution to the consensus problem in a synchronous message-passing system.

(a) Why will the algorithm fail for 4f ≥ n > 3f?

(b) Even though the algorithmis not correct for 4f ≥ n > 3f, under some circumstance(s), the correct processors will end up with the same value. Characterize one such circumstance, independent of the behavior of the malicious processes.

(c) To derive a correct solution for 4f > n > 3f, change line (1k) to read:

if mult > f Will this solution work?

(d) To derive another correct solution for 4f ≥ n > 3f, run the algorithm for 4(f + 1)

rounds instead of for 2(f+1) rounds of the original algorithm. Will this solution work?