Sublinear Algorithms in T-interval Dynamic Networks
Irvan Jahja, Haifeng Yu · 2020
We consider standard T-interval dynamic networks, under the synchronous timing model and the broadcast CONGEST model. In a T-interval dynamic network, the set of nodes is always fixed and there are no node failures. The edges in the network are always undirected, but the set of edges in the topology may change arbitrarily from round to round, as determined by some adversary and subject to the following constraint: For every T consecutive rounds, the topologies in those rounds must contain a common connected spanning subgraph. Let Hr to be the maximum (in terms of number of edges) such subgraph for round r through r+T-1. We define the backbone diameter d of a T-interval dynamic network to be the maximum diameter of all such Hr's, for r ≥ 1. We use n to denote the number of nodes in the network.