Homework answers / question archive / Consider a complete binary rooted tree of n nodes

Consider a complete binary rooted tree of n nodes

Computer Science

Share With

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}. 1. [2 pts] Give a description of the algorithm, the pseudocode, and prove correctness. 2. [2 pts] Analyze the number of rounds. 3. [1 pts] Analyze the total number of messages. 4. [1 pts] Analyze the total number of bits. 5. [4 pts] Extend the algorithm to arbitrary rooted trees.