5.3

(a) Modify Algorithm 15 to achieve consensus within f rounds, in the case f=n-1.

(b) Show that is a lower bound on the number of rounds required in this case.

Algorithm 18 k-set consensus algorithm in the presence of crash failures: code for processor pi, 0in-1. Initially V = {x} 1: round r, 1rs +1: // assume that k divides f send V to all processors 2: 3: 4: 5: ifr receive S; from pj, 0 in-1,ji V = VUUS j=0 f/k+1 then y = min(V) // decide