Achieving Sublinear Complexity under Constant ๐ in ๐ -interval Dynamic Networks
No Thumbnail Available
Date
2022-05-26
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This paper considers standard {\em $T$-interval dynamic networks}, where the $N$ nodes in the network proceed in lock-step {\em rounds}, and where the topology of the network can change arbitrarily from round to round, as determined by an {\em adversary}. The adversary promises that in every $T$ consecutive rounds, the $T$ (potentially different) topologies in those $T$ rounds contain a common connected subgraph that spans all nodes.
Within such a context, we propose novel algorithms for solving some fundamental distributed computing problems such as Count/Consensus/Max.
Our algorithms are the first algorithms whose complexities do not contain an $\Omega(N)$ term, under constant $T$ values. Previous sublinear algorithms require significantly larger $T$ values.