Paper Info
Title
Optimal Collision/Conflict-Free Distance-2 Coloring in Wireless Synchronous Broadcast/Receive Tree Networks
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 known 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 conflictfree, 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. Index Terms-Broadcast/receive communication, Collision, Conflict, Distance-2 graph coloring, Message-passing, Network traversal, Synchronous system, Time slot assignment, Tree network, Wireless network.
Year
DOI
Venue
2016
10.1109/ICPP.2016.47
2016 45th International Conference on Parallel Processing (ICPP)
Keywords
Field
DocType
Broadcast/receive communication,Collision,Conflict,Distance-2 graph coloring,Message-passing,Network traversal,Synchronous system,Time slot assignment,Tree network,Wireless network
Graph theory,Broadcasting,Wireless,Computer science,Parallel computing,Computer network,Models of communication,Time complexity,Time division multiple access,Message passing,Tree network
Conference
Volume
ISSN
ISBN
abs/1601.03225
0190-3918
978-1-5090-2824-5
Citations 
PageRank 
References 
2
0.40
18
Authors
3
Name
Order
Citations
PageRank
Davide Frey118615.95
Hicham Lakhlef211216.86
Michel Raynal34078349.46