Skip to Main content Skip to Navigation

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

Davide Frey 1 Hicham Lakhlef 1 Michel Raynal 1, * 
* Corresponding author
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.
Document type :
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Michel Raynal Connect in order to contact the contributor
Submitted on : Tuesday, January 5, 2016 - 1:21:45 AM
Last modification on : Wednesday, February 2, 2022 - 3:51:00 PM
Long-term archiving on: : Thursday, April 7, 2016 - 2:56:05 PM


Files produced by the author(s)


  • HAL Id : hal-01248428, version 2


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⟩



Record views


Files downloads