EXERCISE 7. Consider an algorithm that operates on a signature r with - a static unary function VAL mapping node identifiers to numerical values, - a dynamic unary function SEND also mapping node identifiers to numerical values, - a dynamic unary message function MESSAGE that maps node identifiers to numerical values or unknown, - a dynamic function STATUS that maps node identifiers to the values unknown or leader, and - a constant N. Suppose that in an initial state we have SEND(i) = VAL(i), IN(i) = unknown, and STATUS(i) unknown for all i. Further assume that val(i) # VAL() holds for i #j. The algorithm iterates the following rule: forall i with 0 VAL(i) then SEND(i):= MESSAGE(i) endif if MESSAGE(i) unknown A MESSAGE(i) = VAL(i) then STATUS(i) := leader endif endpar enddo So the algorithm terminates, when STATUS(i) = leader holds for one i. (i) Show that the algorithm will terminate, and in a final state there will be exactly one i with STATUS(i) = leader. (ii) Determine the worst-case complexity of the algorithm. EXERCISE 7. Consider an algorithm that operates on a signature r with - a static unary function VAL mapping node identifiers to numerical values, - a dynamic unary function SEND also mapping node identifiers to numerical values, - a dynamic unary message function MESSAGE that maps node identifiers to numerical values or unknown, - a dynamic function STATUS that maps node identifiers to the values unknown or leader, and - a constant N. Suppose that in an initial state we have SEND(i) = VAL(i), IN(i) = unknown, and STATUS(i) unknown for all i. Further assume that val(i) # VAL() holds for i #j. The algorithm iterates the following rule: forall i with 0 VAL(i) then SEND(i):= MESSAGE(i) endif if MESSAGE(i) unknown A MESSAGE(i) = VAL(i) then STATUS(i) := leader endif endpar enddo So the algorithm terminates, when STATUS(i) = leader holds for one i. (i) Show that the algorithm will terminate, and in a final state there will be exactly one i with STATUS(i) = leader. (ii) Determine the worst-case complexity of the algorithm