Coloring Fast with Broadcasts
| Autor: | Flin, Maxime, Ghaffari, Mohsen, Halldórsson, Magnús M., Kuhn, Fabian, Nolin, Alexandre |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We present an $O(\log^3\log n)$-round distributed algorithm for the $(\Delta+1)$-coloring problem, where each node broadcasts only one $O(\log n)$-bit message per round to its neighbors. Previously, the best such broadcast-based algorithm required $O(\log n)$ rounds. If $\Delta \in \Omega(\log^{3} n)$, our algorithm runs in $O(\log^* n)$ rounds. Our algorithm's round complexity matches state-of-the-art in the much more powerful CONGEST model [Halld\'orsson et al., STOC'21 & PODC'22], where each node sends one different message to each of its neighbors, thus sending up to $\Theta(n\log n)$ bits per round. This is the best complexity known, even if message sizes are unbounded. Our algorithm is simple enough to be implemented in even weaker models: we can achieve the same $O(\log^3\log n)$ round complexity if each node reads its received messages in a streaming fashion, using only $O(\log^3 n)$-bit memory. Therefore, we hope that our algorithm opens the road for adopting the recent exciting progress on sublogarithmic-time distributed $(\Delta+1)$-coloring algorithms in a wider range of (theoretical or practical) settings. Comment: 42 pages. To appear in proceedings of SPAA 2023 |
| Databáze: | arXiv |
| Externí odkaz: |
|