Distributed colouring and communication in rings with local knowledge
(2004) In Combinatorics, Probability & Computing 13(2). p.123136 Abstract
 We consider two interrelated tasks in a synchronous nnode ring: distributed constant colouring and local communication. We investigate the impact of the amount of knowledge available to nodes on the time of completing these tasks. Every node knows the labels of nodes up to a distance r from it, called the knowledge radius. In distributed constant colouring every node has to assign itself one out of a constant number of colours, so that adjacent nodes get different colours. In local communication every node has to communicate a message to both of its neighbours. We study these problems in two popular communication models: the oneway model, in which each node can only either transmit to one neighbour or receive from one neighbour, in any... (More)
 We consider two interrelated tasks in a synchronous nnode ring: distributed constant colouring and local communication. We investigate the impact of the amount of knowledge available to nodes on the time of completing these tasks. Every node knows the labels of nodes up to a distance r from it, called the knowledge radius. In distributed constant colouring every node has to assign itself one out of a constant number of colours, so that adjacent nodes get different colours. In local communication every node has to communicate a message to both of its neighbours. We study these problems in two popular communication models: the oneway model, in which each node can only either transmit to one neighbour or receive from one neighbour, in any round, and the radio model, in which simultaneous receiving from two neighbours results in interference noise. Hence the main problem in fast execution of the above tasks is breaking symmetry with restricted knowledge of the ring. We show that distributed constant colouring and local communication are tightly related and one can be used to accomplish the other. Also, in most situations the optimal time is the same for both of them, and it strongly depends on the knowledge radius. For knowledge radius r = 0, i.e., when each node knows only its own label, our bounds on time for both tasks are tight in both models: the optimal time in the oneway model is Theta(n), while in the radio model it is Theta(log n). For knowledge radius r = 1 both tasks can be accomplished in time 0(log log n) in the oneway model, if the ring is oriented. For 2 less than or equal to r less than or equal to clog(*) n, where c < 1/2 the upper bounds on time are 0(log ((2r)) n) in the oneway model and 0(log((2[r/2])) n) in the radio model; the lower bound is Omega(log(*) n), in both models. For r greater than or equal to (log(*) n)/2 both tasks can be completed in constant time, in the oneway model, and distributed constant colouring also in the radio model. Finally, if r greater than or equal to log(*) n then constant time is also enough for local communication in the radio model. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/281036
 author
 Dessmark, Anders ^{LU} and Pelc, A
 organization
 publishing date
 2004
 type
 Contribution to journal
 publication status
 published
 subject
 in
 Combinatorics, Probability & Computing
 volume
 13
 issue
 2
 pages
 123  136
 publisher
 Cambridge University Press
 external identifiers

 wos:000220908000001
 scopus:3142539294
 ISSN
 14692163
 DOI
 10.1109/IPDPS.2001.925025
 language
 English
 LU publication?
 yes
 id
 1c8e794cd8f1469691120f53ae5c14cf (old id 281036)
 date added to LUP
 20071023 13:43:30
 date last changed
 20170101 05:12:20
@article{1c8e794cd8f1469691120f53ae5c14cf, abstract = {We consider two interrelated tasks in a synchronous nnode ring: distributed constant colouring and local communication. We investigate the impact of the amount of knowledge available to nodes on the time of completing these tasks. Every node knows the labels of nodes up to a distance r from it, called the knowledge radius. In distributed constant colouring every node has to assign itself one out of a constant number of colours, so that adjacent nodes get different colours. In local communication every node has to communicate a message to both of its neighbours. We study these problems in two popular communication models: the oneway model, in which each node can only either transmit to one neighbour or receive from one neighbour, in any round, and the radio model, in which simultaneous receiving from two neighbours results in interference noise. Hence the main problem in fast execution of the above tasks is breaking symmetry with restricted knowledge of the ring. We show that distributed constant colouring and local communication are tightly related and one can be used to accomplish the other. Also, in most situations the optimal time is the same for both of them, and it strongly depends on the knowledge radius. For knowledge radius r = 0, i.e., when each node knows only its own label, our bounds on time for both tasks are tight in both models: the optimal time in the oneway model is Theta(n), while in the radio model it is Theta(log n). For knowledge radius r = 1 both tasks can be accomplished in time 0(log log n) in the oneway model, if the ring is oriented. For 2 less than or equal to r less than or equal to clog(*) n, where c < 1/2 the upper bounds on time are 0(log ((2r)) n) in the oneway model and 0(log((2[r/2])) n) in the radio model; the lower bound is Omega(log(*) n), in both models. For r greater than or equal to (log(*) n)/2 both tasks can be completed in constant time, in the oneway model, and distributed constant colouring also in the radio model. Finally, if r greater than or equal to log(*) n then constant time is also enough for local communication in the radio model.}, author = {Dessmark, Anders and Pelc, A}, issn = {14692163}, language = {eng}, number = {2}, pages = {123136}, publisher = {Cambridge University Press}, series = {Combinatorics, Probability & Computing}, title = {Distributed colouring and communication in rings with local knowledge}, url = {http://dx.doi.org/10.1109/IPDPS.2001.925025}, volume = {13}, year = {2004}, }