Skip to Main content Skip to Navigation
Journal articles

Vertex Coloring with Communication Constraints in Synchronous Broadcast Networks

Abstract : This paper considers distributed vertex-coloring in broadcast/receive networks suffering from conflicts and collisions. (A collision occurs when, during the same round, messages are sent to the same process by too many neighbors; a conflict occurs when a process and one of its neighbors broadcast during the same round.) More specifically, the paper focuses on multi-channel networks, in which a process may either broadcast a message to its neighbors or receive a message from at most γ of them. The paper first provides a new upper bound on the corresponding graph coloring problem (known as frugal coloring) in general graphs; proposes an exact bound for the problem in trees; presents a deterministic, parallel, color-optimal, collision-and conflict-free distributed coloring algorithm for trees; proves the correctness of this algorithm; and finally evaluates experimentally its performance using simulations that show our solution clearly outperforms a reference protocol for distributed TDMA slot-allocation.
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/hal-02376726
Contributor : François Taïani <>
Submitted on : Friday, November 22, 2019 - 5:07:23 PM
Last modification on : Saturday, July 11, 2020 - 3:16:21 AM

File

CCMC-journal-version.V3_1_FT_f...
Files produced by the author(s)

Identifiers

Citation

Hicham Lakhlef, Michel Raynal, François Taïani. Vertex Coloring with Communication Constraints in Synchronous Broadcast Networks. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2019, 30 (7), pp.1672-1686. ⟨10.1109/TPDS.2018.2889688⟩. ⟨hal-02376726⟩

Share

Metrics

Record views

111

Files downloads

270