Decipher Siddharth solution to the HW2 problem of 4 processors one Byz, and either approve as correct or give a counter example.
In class we have seen Bracha’s algorithm for reliable broadcast in asynchronous Message Passing system where messages not deleted by the adversary will eventually arrive. With t < n=3 where t is the number of maximum Byz faults and n the number of processors we proved that the algorithm guarantees:
if the broadcaster is correct then all correct processors will output its value of broadcast
if the broadcaster is Byz then if one correct processor will output a value for the broadcast then eventually all correct processors will output same
We know that in a t-resilient asynchronous system we can solve t + 1 election where each correct processor outputs a participating id (we assume complete network of communication so each processor when receiving a message on an input port knows who is the sender). Can we solve this task in the asynchronous Byz? (there is a subtlety here, proc pi might not participate ( it counts against a fault) but other Byz might lie and say she is. I am not sure it can be dealt with, so on first cut allow to output such participant)
