Vertex Coloring with Communication and Local Memory Constraints in Synchronous Broadcast Networks

Hicham Lakhlef 1, * Michel Raynal 1 François Taïani 1
* Auteur correspondant
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : The vertex coloring problem has received a lot of attention in the context of synchronous round-based systems where, at each round, a process can send a message to all its neighbors, and receive a message from each of them. Hence, this communication model is particularly suited to point-to-point communication channels. Several vertex coloring algorithms suited to these systems have been proposed. They differ mainly in the number of rounds they require and the number of colors they use. This paper considers a broadcast/receive communication model in which message collisions and message conflicts can occur (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). This communication model is suited to systems where processes share communication bandwidths. More precisely, the paper considers the case where, during a round, a process may either broadcast a message to its neighbors or receive a message from at most $m$ of them. This captures communication-related constraints or a local memory constraint stating that, whatever the number of neighbors of a process, its local memory allows it to receive and store at most $m$ messages during each round. The paper defines first the corresponding generic vertex multi-coloring problem (a vertex can have several colors). It focuses then on tree networks, for which it presents a lower bound on the number of colors $K$ that are necessary (namely, $K=\lceil\frac{\Delta}{m}\rceil+1$, where $\Delta$ is the maximal degree of the communication graph), and an ssociated coloring algorithm, which is optimal with respect to $K$.
Type de document :
[Research Report] 2035, IRISA; Université de Rennes 1. 2016, pp.23
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger
Contributeur : François Taïani <>
Soumis le : vendredi 8 avril 2016 - 16:40:44
Dernière modification le : vendredi 11 janvier 2019 - 13:52:01
Document(s) archivé(s) le : mardi 15 novembre 2016 - 00:14:39


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01300095, version 1
  • ARXIV : 1604.03356


Hicham Lakhlef, Michel Raynal, François Taïani. Vertex Coloring with Communication and Local Memory Constraints in Synchronous Broadcast Networks. [Research Report] 2035, IRISA; Université de Rennes 1. 2016, pp.23. 〈hal-01300095〉



Consultations de la notice


Téléchargements de fichiers