Communication efficient edge coloring with near optimal colors and local lemma use
Communication-Efficient $(1+\varepsilon)Δ$-Edge Coloring and Lovász Local Lemma
Distributed, Parallel, and Cluster Computing
Summary
The paper addresses the problem of coloring edges in a network when the connections are split between two parties who want to coordinate with minimal communication. The authors develop a new method that allows them to color edges using almost the smallest possible number of colors while exchanging very few messages. Their method relies on a clever way to share random choices with little coordination using a two-party version of an important mathematical tool called the Lovász Local Lemma. This approach also works well for other problems that can be described using this lemma.
What this means in practice
- •For network schedulers: Reduce communication overhead when assigning frequencies or time slots in networks shared by different controllers using near-optimal channel assignments.
- •For parallel computing teams: Coordinate resource allocation across different computing units with limited communication by efficient edge coloring to prevent conflicts.
Authors
Yi-Jun Chang, Nima Dolatabadi, Hung Thuan Nguyen
Abstract
We study edge coloring in the two-party edge-partition model, where Alice and Bob each know part of the edge set and must jointly produce a proper coloring with little communication. Previous work gave a deterministic $(2Δ-1)$-edge-coloring protocol using $O(n)$ bits, leaving open whether fewer colors can be obtained efficiently. We simultaneously reduce both the number of colors and the communication. For every fixed $\varepsilon>0$ and all sufficiently large $Δ$, we give a public-coin Las Vegas protocol that finds a proper $(1+\varepsilon)Δ$-edge coloring using $O(ne^{-γΔ} + 1)$ expected bits and $O\left(\frac{\log n}Δ+1\right)$ expected rounds, where $γ>0$ depends only on $\varepsilon$. Thus, the expected communication is $o(n)$ when $Δ=ω(1)$ and $O(1)$ when $Δ\ge C_\varepsilon\log n$, for a sufficiently large constant $C_\varepsilon$. Using only private coins adds $O(\log n)$ expected bits. Our key idea is a new randomized coloring procedure that allows Alice and Bob to color their edges using essentially the same color space with only a small amount of coordination, so most of their random choices remain private. To make this procedure succeed, we develop a communication-efficient constructive Lovász local lemma (LLL) for two parties. Our two-party constructive LLL is also of independent interest. We illustrate its broader applicability by applying it to standard LLL formulations of several other classical problems, obtaining communication-efficient two-party protocols.