Distributed finite-time calculation of node eccentricities, graph radius and graph diameter

Abstract

The distributed calculation of node eccentricities, graph radius and graph diameter are fundamental steps to tune network protocols (e.g., setting an adequate time-to-live of packets), to select cluster heads, or to execute distributed algorithms, which typically depend on these parameters. Most existing methods deal with undirected topologies and have high memory and/or bandwidth requirements (or simply provide a bound on the diameter to reduce such costs). Other approaches, instead, require nodes able to communicate with their neighbors on a point-to-point basis, thus requiring each node to be aware of its neighbors. In this paper, we consider strongly connected directed graphs or connected undirected graphs, and we develop an algorithm that takes advantage of the robustness and versatility of the max-consensus algorithm, and has low computational, memory and bandwidth requirements. Moreover, the agents communicate by broadcasting messages to their (out-) neighbors without requiring any knowledge on them or needing point-to-point communication capability. Specifically, each node has memory occupation proportional to the number of its neighbors, while the bandwidth for each link at each time instant is O(logn) bits, where n is the number of nodes. The completion time of the proposed algorithm is O(δn) for undirected graphs and O(n2) for directed graphs, where δ is the network diameter. © 2016 Elsevier B.V. All rights reserved.