Skip to Main content Skip to Navigation
Reports

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
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
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 :
Reports
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-01248428
Contributor : Michel Raynal <>
Submitted on : Tuesday, January 5, 2016 - 1:21:45 AM
Last modification on : Thursday, January 7, 2021 - 4:13:15 PM
Long-term archiving on: : Thursday, April 7, 2016 - 2:56:05 PM

Files

D2-coloring-V18.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

3158

Files downloads

270