Consider the Exclusive Read (ER) PRAM Broadcast Algorithm. Suppose there are 16 processors (P1 through P16) and P16 has a value v = 3 that needs to be broadcast. (a) Show the steps (and during step 2, the iterations) required to store the value in P16 in all processors. (b) Let's say that during iteration 2 (where i=2), P2 suffers a failure such that it writes 4 instead of 3. Show how this change affects the final state of the memory by drawing the memory locations. (See example below)

In the ER broadcast algorithm, suppose processor P3 fails after the second iteration of the for loop, but magically all other processor and the rest of the system continue to function. What would be the consequence? P3 wont be able to copy to X7; P7 will read the wrong value from X7 and P15 would read the wrong value from X15

Example Suppose there are 16 processors and P7 has a value v-1 that needs to be broadcast. Step 1: Pi initially writes 1 into X1 Step 2 P1 reads 1 from X1 P1 writes 1 to X2 P1 reads 1 from Xl P2 reads 1 from X2 P1 writes 1 to X3 P2 writes 1 to X4 P1 reads 1 from X1 P2 reads 1 from X2 P3 reads 1 from X3 P4 reads 1 from X4 P1 writes 1 to X5 P2 writes 1 to X6 P3 writes 1 to X7 P4 writes 1 to X8 P1 reads 1 from X1 P2 reads 1 from X2 P3 reads 1 from X3 P4 reads 1 from X4 P5 reads 1 from X5 P6 reads 1 from X6 P7 reads 1 from X7 P8 reads 1 from XS P1 writes 1 to X9 P2 writes 1 to X10 P3 writes 1 to X11 P4 writes 1 to X12 P5 writes 1 to X13 P6 writes 1 to X14 P7 writes 1 to X15 P8 writes 1 to X16 Step 3 P1 reads 1 from X1 P2 reads 1 from X2 P3 reads 1 from X3 P4 reads 1 from X4 P5 reads 1 from X5 P6 reads 1 from X6 P7 reads 1 from X7 P8 reads 1 from X8 P9 reads 1 from X9 P10 reads 1 from X10 P11 reads from X11 P12 reads 1 from X12 P13 reads 1 from X13 P14 reads 1 from X14 P15 reads 1 from X15 P16 reads 1 from X16 Steps 1 and 3 take O(1) time. Step 2 is done O(log n) times and each of those takes O(1) time. So the total time is O(log n). In fact, it is (lgn] Example Suppose there are 16 processors and P7 has a value v-1 that needs to be broadcast. Step 1: Pi initially writes 1 into X1 Step 2 P1 reads 1 from X1 P1 writes 1 to X2 P1 reads 1 from Xl P2 reads 1 from X2 P1 writes 1 to X3 P2 writes 1 to X4 P1 reads 1 from X1 P2 reads 1 from X2 P3 reads 1 from X3 P4 reads 1 from X4 P1 writes 1 to X5 P2 writes 1 to X6 P3 writes 1 to X7 P4 writes 1 to X8 P1 reads 1 from X1 P2 reads 1 from X2 P3 reads 1 from X3 P4 reads 1 from X4 P5 reads 1 from X5 P6 reads 1 from X6 P7 reads 1 from X7 P8 reads 1 from XS P1 writes 1 to X9 P2 writes 1 to X10 P3 writes 1 to X11 P4 writes 1 to X12 P5 writes 1 to X13 P6 writes 1 to X14 P7 writes 1 to X15 P8 writes 1 to X16 Step 3 P1 reads 1 from X1 P2 reads 1 from X2 P3 reads 1 from X3 P4 reads 1 from X4 P5 reads 1 from X5 P6 reads 1 from X6 P7 reads 1 from X7 P8 reads 1 from X8 P9 reads 1 from X9 P10 reads 1 from X10 P11 reads from X11 P12 reads 1 from X12 P13 reads 1 from X13 P14 reads 1 from X14 P15 reads 1 from X15 P16 reads 1 from X16 Steps 1 and 3 take O(1) time. Step 2 is done O(log n) times and each of those takes O(1) time. So the total time is O(log n). In fact, it is (lgn]