Question: Distributed Computation of the Number of Nodes in a Network. Consider a strongly connected communication network with N nodes and A (bidirectional) links. Each node knows its identity and the set of its immediate neighbors but not the network topology. Node 1 wishes to determine the number of nodes in the network. As a first step, it initiates an algorithm for finding a directed, rooted spanning tree with node 1 as the root. By this we mean a tree each link (i, k) of which is directed and oriented toward node 1 along the unique path on the tree leading from i to 1 (see the example tree shown in Fig.).
(a) Devise a distributed algorithm involving exchange of messages between nodes that constructs such a tree. The algorithm is initiated by node I and should involve no more than O(A) message transmissions. Communication along any link is assumed error-free. At the end of the algorithm, the end nodes of each link should know whether the link is part of the tree, and, if so, they should know its direction.
(b) Supplement the algorithm derived in part (a) by another algorithm involving no more than O(N) message transmissions by means of which node 1 gets to know N.
(c) Assuming that each message transmission takes an equal amount of time T, derive an upper bound for the time needed to complete the algorithms in parts (a) and (b).