Rabin’s algorithm for Byzantine Generals Problem.Notes by Sanjeev Arora, Fall 1995 (updated Fall 2005)Byzantine Generals Problem: There are n = 3t + 1 processors and at least2t + 1 of them are working correctly. (The remaining t could be arbitrarilymisbehaved or faulty.) Initially, processor i holds a bit bi∈ {0, 1}. The goalis for them to exchange messages and agree upon a bit bfinal. If all bifor thegood processors were the same, then we require bfinalto be that same bit.Otherwise there is no hard requirement on what bfinalshould be so long as allgood processors agree what it is.Sometimes this problem is also called Byzantine Agreement. It can be solvedwith a deterministic algorithm in poly(n) steps. It is known that no distributedalgorithm exists if the number of faulty processors exceeds n/3.Now we describe a simple randomized algorithm due to Rabin which assumesthat there is a global random coin that is tossed at each step, and which isvisible to all processors.The processors maintain at all times a bit, vote, which is initially biforprocessor i. At the start of each round each processor sends its vote valueto every other processor. Each processor examines all 3t + 1 values of voteit receives (including its own). It identifies maj = the majority bit amongthese values of vote, and tally = the number of times it saw this bit amongthe vote values. Notice, the values of maj and tally can vary widely amongthe processors, since a faulty/malicious processors could try to confuse thingsby sending different values of vote to different processors.Each processor now applies the following algorithm at each step.Do the following depending upon the value of tally:1. tally ≥ 2t + 1: Set vote = maj.2. tally ≤ 2t: Look at global-coin-toss. If it is ‘‘Heads," thenset vote = 1, else set vote = 0.Proof of Correctness: Note that if all the good processors have the sameinitial value, then they all set their votes to this value in the first round. Inall other cases, we show that with probability at least 1/2, all the processorsassign the same value to vote. (Note that as soon as this happens, then fromthen on, tally ≥ 2t + 1 for all processors, and so all processors will continueexecuting line (1) in the algorithm.)There are two cases. (i) Some processor sees tally ≥ 2t + 1, and maj = b forsome b ∈ {0, 1}. Since only t processors are faulty, we conclude that at leastt + 1 good processors must have sent b as their value of vote. Thus no otherprocessor will see both tally ≥ 2t + 1 and maj = 1 − b in the same round.Hence regardless of whether the other processors execute step (1) or (2) in theabove algorithm, the probability is at least 1/2 that they will all set vote to b.1(ii) No good processor sees tally ≥ 2t + 1. Then all of them execute step (2),and with probability 1 set vote to the same value.It is a homework exercise to modify the algorithm so that processors candetect when the algorithm has succeeded (namely, all good processors have thesame value of