Problem
Consider a complete binary rooted tree of n nodes. Each leaf v holds a certain integer value x 2 0. Give an efficient distributed algorithms so that all the nodes of the tree learn the correct value of max { To : v is a leaf}.
a) Give a description of the algorithm, the pseudocode, and prove correctness.
b) Analyze the number of rounds.
c) Analyze the total number of messages.
d) Analyze the total number of bits.
e) Extend the algorithm to arbitrary rooted trees.