3. Consider the followingalgorithm to solve general Byzantine consensus, given a

ID: 3616409 • Letter: 3

Question

3. Consider the followingalgorithm to solve general Byzantine consensus, given asolution

for binary consensus. Everyprocess p usesthree private variables: one to store the

initial value,secondary-valuep and votep. Some default value is xedacross all the

processes. The following is acode for process p.

Preliminary round:Process pbroadcasts its initial value.

sets its votep to 1, otherwise to0. Processp sets itssecondary-valuep to

the majority of vote valuesreceived, if such a strict majority exists, otherwise

to a default value.

Following rounds:An algorithm, say, A for binary consensus is run,with the

values of vote treated as initialvalues.

If process p decides on vote value1 in the executionof A,then p'snal

decision is on itssecondary-valuep, otherwise the nal decision is on the

default value.

(a) Is this a correct reductionfor f < n=3?

If you believe that this is thecase, then prove the fact, which completes your

solution, otherwise give acounter-example and proceed to the next point.

(b) Is this a correct reductionfor f < n=4?

If you believe that this is thecase, then prove the fact, which completes your

solution, otherwise give acounter-example and proceed to the next point.

consensus, that uses only onepreliminary round of communication, and is correct

for f< n=4.

If you are at this point, thenyou do believe that the given algorithm is not a

correct reduction, as justi edby your counter-examples

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.