I need to show that in the CONGEST model, the diameter of a (connected) network can be calculated in $ O(m) $ rounds, with $ m $ indicating the number of edges of the network.

My idea would be the following: First a leader is determined by using the radius-growth algorithm which has a runtime of $ O (n) $ rounds. Because $ n \leq m – 1$ , that works.

After the leader was determined, the leader starts a BFS, which needs $ O(D)$ rounds (with $ D $ being the diameter of the network, which is at that point unknown, but of course $ D \leq m $ ). Then we can determine the node with the highest distance from the leader in $ O(D) $ rounds, let’s call this node $ a $ . Then we start another BFS from the node $ a $ and, again, determine the node with the highest distance from $ a $ , let’s call this node $ b $ . Then $ dist(a, b)$ should be the diameter $ D $ of the network.

The runtime seems to be okay, so it would be possible in $ O (m) $ rounds with this approach. The only problem I have is that I am not sure if this approach is correct, at least I am not able to prove it formally. I need to prove, if the $ dist(a, b) = D$ , then the two BFS find the nodes $ a $ and $ b$ . My idea would be that if the leader, which is determined by using the radius-growth algorithm, is either the node $ a $ or $ b $ , then trivially it would be correct. If it is neither $ a $ nor $ b $ (nor any other node at the ‘start’ or ‘end’ of a path with length $ D $ ), then during the first BFS we would at some point reach the path which represents the diameter. If without loss of generality the node $ b $ has a higher distance to the leader, then the leader would find $ b$ after the first BFS, because if it would find another node (let’s call this node $ x $ ), then $ dist(a, b) \neq D $ , because $ dist(a, x) $ would be the diameter and not $ dist(a, b)$ which would be a contradiction.

Is that right?