TY - JOUR
T1 - Single round simulation on radio networks
AU - Alon, Noga
AU - Bar-Noy, Amotz
AU - Linial, Nathan
AU - Peleg, David
N1 - Funding Information:
A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given *An abstract of this paper appeared in “Proceedings, 21st Symp. on Theory of Computing, 1989,” pp. 274-285. ‘This work was carried out while this author was visiting IBM Almaden Research Center. Supported in part by a Bergmann Memorial grant. ‘This work was carried out while this author was visiting IBM Almaden Research Center and Stanford University. ‘This work was carried out while this author was visiting Stanford University. Supported in part by a Weizmann fellowship, by Contract ONR NOO14-85-C-0731 and by a grant of Stanford Center for Integrated Systems. “This work was carried out while this author was visiting Stanford University. Supported in part by Contract ONR NOOO14-85-C-0731 and by a grant of Stanford Center for Integrated Systems.
PY - 1992/6
Y1 - 1992/6
N2 - A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then and precisely one of its neighbors transmits. This stringent rule poses serious difficulties in performing even the simplest tasks. This is true even under the overly optimistic assumptions of centralized coordination and complete knowledge of the network topology. We look at the question of simulating two of the standard message-passing models on a radio network. In the general message-passing model, a processor may send each of its outgoing neighbors a possibly different message in each round. In the uniform message-passing model, in each round a processor must send an identical message to all its outgoing neighbors. Both message-passing models can easily simulate the radio model with no overhead. In the other direction, we propose and study a primitive called the single-round simulation (SRS), enabling the simulation of a single round of an algorithm designed for the standard message models. We give lower bounds for the length of SRS schedules for both models and supply constructions or existence proofs for schedules of matching (or almost matching) lengths.
AB - A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then and precisely one of its neighbors transmits. This stringent rule poses serious difficulties in performing even the simplest tasks. This is true even under the overly optimistic assumptions of centralized coordination and complete knowledge of the network topology. We look at the question of simulating two of the standard message-passing models on a radio network. In the general message-passing model, a processor may send each of its outgoing neighbors a possibly different message in each round. In the uniform message-passing model, in each round a processor must send an identical message to all its outgoing neighbors. Both message-passing models can easily simulate the radio model with no overhead. In the other direction, we propose and study a primitive called the single-round simulation (SRS), enabling the simulation of a single round of an algorithm designed for the standard message models. We give lower bounds for the length of SRS schedules for both models and supply constructions or existence proofs for schedules of matching (or almost matching) lengths.
UR - http://www.scopus.com/inward/record.url?scp=38249013511&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38249013511&partnerID=8YFLogxK
U2 - 10.1016/0196-6774(92)90015-5
DO - 10.1016/0196-6774(92)90015-5
M3 - Article
AN - SCOPUS:38249013511
SN - 0196-6774
VL - 13
SP - 188
EP - 210
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 2
ER -