We can treat the scheduler as anad versary who uses the knowledge of our protocols and input values to frustrate our attempts at reaching consensus. One way to outwit an adversary is through...

We can treat the scheduler as anad versary who uses the knowledge of our protocols and input values to frustrate our attempts at reaching consensus. One way to outwit an adversary is through randomization. Assume that there are two threads that want to reach consensus, each of which can flip an unbiased coin, and that the adversary cannot control future coin flips but can observe the result of each coin flip and each value read or written. The adversary scheduler can stop a thread before or after a coin flip or a read or write to a shared register. Ar and omized consen sus protocol terminates with probability arbitrarily close to 1 (given sufficiently longtime) against an adversary scheduler. shows a plausible-looking randomized binary consensus protocol. Give an example showing that this protocol is incorrect.

• Does the algorithm satisfy the safety properties of consensus (i.e., validity and consistency)? That is, is it true that each thread can only output a value that is the input of one of the two threads, and also that the outputs cannot be different?

• Does it terminate with a probability arbitrarily close to 1?