Achieving Sublinear Complexity under Constant 𝑇 in 𝑇 -interval Dynamic Networks

dc.contributor.authorHou, Ruomu
dc.contributor.authorJahja, Irvan
dc.contributor.authorSun, Yucheng
dc.contributor.authorWu, Jiyan
dc.contributor.authorYu, Haifeng
dc.date.accessioned2022-06-02T02:53:30Z
dc.date.available2022-06-02T02:53:30Z
dc.date.issued2022-05-26
dc.description.abstractThis 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.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/11727
dc.language.isoen_USen_US
dc.titleAchieving Sublinear Complexity under Constant 𝑇 in 𝑇 -interval Dynamic Networksen_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
adaptivewalk-spaa22-tr.pdf
Size:
571.53 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description: