Distributed Vertex Coloring in Bandwidth Constrained Models

Abstract

This thesis studies the $(\Delta+1)$-coloring problem in message-passing models under severe bandwidth constraints. In those models, a network of $n$ computers is modeled as a graph $G$ with $n$ vertices that communicate in synchronous rounds over the edges of the graph. Our goal is to devise an algorithm with the smallest possible number of rounds at the end of which each vertex picks a color in $\set{1, 2, \ldots, \Delta+1}$ --- where $\Delta$ is the maximum degree of $G$ --- such that adjacent vertices have different colors. This task is central to distributed graph algorithms for it models symmetry breaking challenges ubiquitous in network computing and large-scale computing. Despite its simplicity in the centralized setting, and considerable attention since the seminal work of Linial (\emph{SIAM J.\ Comput.}, 1992) that introduced distributed graph algorithms, the complexity of $(\Delta+1)$-coloring remains poorly understood. In recent years, a series of developments culminated in the first $\poly(\log\log n)$-round algorithm for $(\Delta+1)$-coloring, achieved by Chang, Li, and Pettie (\emph{SIAM J.\ Comput.}, 2020) jointly with Rozhon and Ghaffari (\emph{STOC}, 2020). Shortly thereafter, Halld\'orsson, Kuhn, Maus, and Tonoyan (\emph{STOC}, 2021) further showed that this complexity is achievable with small $O(\log n)$-bit messages. Still, their algorithm requires strong forms of centralization. This prompted us to explore how severe bandwidth constraints affect the ability of distributed networks to get $(\Delta+1)$-colored fast, making a threefold contribution. First, we show that distributed graphs in which nodes merely broadcast one $O(\log n)$-bit message per round can be $(\Delta+1)$-colored in $\poly(\log\log n)$ rounds, and even in $O(\log^*n)$ rounds when $\Delta$ is at least polylogarithmic. This broadcast constraint severely limits nodes, which might otherwise emit as many as $O(n\log n)$ bits per round. In fact, our algorithm is simple enough to be implemented in even weaker models, achieving the same $\poly(\log\log n)$ round complexity if each node reads its received messages in a streaming fashion, using only $\poly(\log n)$-bit of memory. Second, we further reduce the number of bits emitted and received by each vertex. We design a distributed algorithm that $(\Delta+1)$-colors a graph in $O(\log^2 \Delta) + \poly(\log\log n)$ rounds using $O(\log n)$-bit messages, with vertices communicating with $O(\log^4 n)$ other vertices. At the heart of this algorithm is an extension of the celebrated palette sparsification theorem by Assadi, Chen, and Khanna (\emph{SODA}, 2019). They show that to $(\Delta+1)$-color a graph, it suffices if every vertex limits its color choice to $O(\log n)$ independently sampled colors in $\set{1, 2, \ldots, \Delta+1}$. However, computing the resulting coloring required a centralized approach. The main result of this part is a distributed palette sparsification theorem: a $O(\log^2 \Delta)$-round algorithm for $(\Delta+1)$-coloring the graph given random lists of $O(\log^2 n)$ random colors per node. We also prove that any algorithm of this kind has round complexity $\Omega\paren*{\frac{\log \Delta}{\log\log n}}$. Finally, we color virtual graphs: graphs locally embedded within the communication network. It can be seen as an intermediate setting between that of the first and second parts, where vertices can interact with all their neighbors but only through processes akin to aggregation on trees. Besides generalizing classical distributed graph coloring, this captures other previously studied settings, including cluster graphs and power graphs. We show that the complexity of coloring a virtual graph depends on the dilation $\dilation$ and edge congestion $\congestion$ of its embedding. Surprisingly, we find that virtual graphs can be colored nearly as fast as ordinary graphs. Namely, we give a $O(\congestion\dilation\cdot \log^*n)$-round algorithm for virtual graphs with $\Delta$ at least polylogarithmic and a $\congestion\dilation \cdot \poly(\log\log n)$-round algorithm for graphs with $\Delta \leq \poly(\log n)$. This shows that the $(\Delta+1)$-coloring problem can be solved quickly even when the nodes themselves are decentralized.