Diogo Lima, Hugo Miranda, and François Taïani

Weighting Past on the Geo-Aware State Deployment Problem (Short Paper)

19th IEEE International Symposium on A World of Wireless, Mobile and Multimedia Networks (WoWMoM 2018), Chania, Greece, June, pp. 1-3, IEEE Computer Society, 2018

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 gamma 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, and presents a deterministic, parallel, color-optimal, collision- and conflict-free distributed coloring algorithm for trees, and proves its correctness.

doi: http://doi.org/10.1109/WoWMoM.2018.8449808 (publisher's link)


Copies / Update: Please contact me by email if you wish to obtain a copy of a paper that is not available on line.

[Maison.png]Back to Home

Last generated on 5 Feb 2020       francois.taiani@irisa.fr     Valid HTML 4.0!