
Given a palette P of at most ξ colors, and a parameter d, a (d,ξ)-coloring of a graph is an assignment of a color from the palette P to every node in the graph such that any two nodes at distance at most d have different colors. We prove that for every n-node unit disk graph with maximum degree Δ, there exists a distributed algorithm computing a (1,O(Δ))-coloring under the SINR (Signal-to-Interference-plus-Noise Ratio) physical model in at most O(Δlogn) time slots, which is optimal up to a logarithmic factor. Our result is based on revisiting a previous coloring algorithm, due to T. Moscibroda and R. Wattenhofer, described in the so called graph-based model~\cite{MW08}. We also prove that, for a well defined constant d, a (d,O(Δ))-coloring allows us to schedule an interference free TDMA-like MAC protocol under the physical SINR constraints. As a corollary, any uniform interference-free message passing algorithm with running time τ can be simulated in the SINR model in O(Δ(logn+τ)) time slots. The latter generic result provides new insights into the distributed scheduling of radio network tasks under the harsh SINR constraints.
Distributed Algorithm, TDMA, Time Complexity, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Coloring, SINR Model
Distributed Algorithm, TDMA, Time Complexity, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Coloring, SINR Model
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 16 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
