Consider the following algorithm to solve the general Consensus with Byzantine faults, given a solution A for the binary Consensus. Every process p uses three private vari- ables, to store the initial value, secondary-valuep, and votep. Some default value is fixed, the same for all processes. The following is the pseudo-code for a process p.

The preliminary round: Process p broadcasts its initial value. If at least nf copies of a certain value were received by process p, thenp sets its votep to 1, otherwise to 0. Process p sets its secondary-valuepto the majority of values received, if such a strict majority exists, oth- erwise to the default value.

The following rounds: Algorithm A for binary consensus is run, with the votevalues treated as the initial values. If process p decides on the vote value 1 in the execution of A, then ps final decision is on its secondary-valuep, otherwise the final decision is on the default value.

(a) Is this a correct reduction when f < n/3? If you believe that this is the case, then prove the fact, which completes your solution, otherwise give a counter-example and proceed to the next point.

(b) Is this a correct reduction when f < n/4? If you believe that this is the case, then prove the fact, which completes your solution, otherwise give a counter-example and proceed to the next point.

(c) Develop a correct reduction of general Byzantine Consensus to binary Byzantine Consensus with the following two properties: (1) it uses only one preliminary round of communication, and (2) it is correct when f < n/4.

If you are at this point, then you do not believe that the algorithm given above is a correct reduction, even for f < n/4, as justified by your two counter-examples.