Optimal Collision/Conflict-free Distance-2 Coloring in Synchronous Broadcast/Receive Tree Networks

Davide Frey 1 Hicham Lakhlef 1 Michel Raynal 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 : This article is on message-passing systems where communication is (a) synchronous and (b) based on the " broadcast/receive " pair of communication operations. " Synchronous " means that time is discrete and appears as a sequence of time slots (or rounds) such that each message is received in the very same round in which it is sent. " Broadcast/receive " means that during a round a process can either broadcast a message to its neighbors or receive a message from one of them. In such a communication model, no two neighbors of the same process, nor a process and any of its neighbors, must be allowed to broadcast during the same time slot (thereby preventing message collisions in the first case, and message conflicts in the second case). From a graph theory point of view, the allocation of slots to processes is know as the distance-2 coloring problem: a color must be associated with each process (defining the time slots in which it will be allowed to broadcast) in such a way that any two processes at distance at most 2 obtain different colors, while the total number of colors is " as small as possible ". The paper presents a parallel message-passing distance-2 coloring algorithm suited to trees, whose roots are dynamically defined. This algorithm, which is itself collision-free and conflict-free, uses ∆ + 1 colors where ∆ is the maximal degree of the graph (hence the algorithm is color-optimal). It does not require all processes to have different initial identities, and its time complexity is O(d∆), where d is the depth of the tree. As far as we know, this is the first distributed distance-2 coloring algorithm designed for the broadcast/receive round-based communication model, which owns all the previous properties.
Type de document :
Rapport
[Research Report] 2030, IRISA, Inria Rennes. 2015, pp.19
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01248428
Contributeur : Michel Raynal <>
Soumis le : mardi 5 janvier 2016 - 01:21:45
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : jeudi 7 avril 2016 - 14:56:05

Fichiers

D2-coloring-V18.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01248428, version 2

Citation

Davide Frey, Hicham Lakhlef, Michel Raynal. Optimal Collision/Conflict-free Distance-2 Coloring in Synchronous Broadcast/Receive Tree Networks. [Research Report] 2030, IRISA, Inria Rennes. 2015, pp.19. 〈hal-01248428v2〉

Partager

Métriques

Consultations de la notice

1285

Téléchargements de fichiers

90