Achieving Sublinear Complexity under Constant 𝑇 in 𝑇 -interval Dynamic Networks
| dc.contributor.author | Hou, Ruomu | |
| dc.contributor.author | Jahja, Irvan | |
| dc.contributor.author | Sun, Yucheng | |
| dc.contributor.author | Wu, Jiyan | |
| dc.contributor.author | Yu, Haifeng | |
| dc.date.accessioned | 2022-06-02T02:53:30Z | |
| dc.date.available | 2022-06-02T02:53:30Z | |
| dc.date.issued | 2022-05-26 | |
| dc.description.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. | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/11727 | |
| dc.language.iso | en_US | en_US |
| dc.title | Achieving Sublinear Complexity under Constant 𝑇 in 𝑇 -interval Dynamic Networks | en_US |
| dc.type | Technical Report | en_US |