ALGORITHMIC PROBLEMS IN RADIO NETWORKS
by
Mariusz, A. Rokicki
M.S., Computer Science, University of Warsaw, 1999
B.A., Computer Science, University of Warsaw, 1997
A thesis submitted to the
University of Colorado at Denver
and Health Sciences Center
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Computer Science and Information Systems
2007
This thesis for the Doctor of Philosophy
degree by
Mariusz, A. Rokicki
has been approved
by
Michael V. Mannino
Rokicki, Mariusz, A. (Ph.D., Computer Science and Information Systems, Com
puter Science and Engineering, UCDHSC)
Algorithmic Problems in Radio Networks
Thesis directed by Associate Professor Bogdan S. Chlebus
ABSTRACT
We investigate algorithmic aspects of communication protocols in multihop
packet radio networks and the multiple access channel. Radio networks model
wireless data communication with arbitrary topology of direct transmissions
when the bandwidth is limited to one wave frequency. A multipleaccess chan
nel is a system in which a transmission delivers the message to all nodes. Both
these types of networks share the property that multiple packets arriving simul
taneously at a node result in mutual interference, which prevents receiving the
messages successfully by any among the recipients.
The fundamental algorithmic goal for networks is to implement useful commu
nication tasks. We consider broadcasting and gossiping among such primitives.
The static broadcast problem is about a scenario in which one source node gen
erates input data that need to be disseminated among all the nodes. In the
dynamic broadcast problem, input data are continuously injected into the nodes
and next are disseminated. The gossip problem starts with all the nodes holding
their individual input data (called rumors), and the goal is for all the nodes to
learn all the rumors.
For multihop radio networks, we initiate an approach to study asynchrony.
We investigate the complexity of static broadcasting in such a setting. Specific
results on gossiping in multihop radio networks concern upper and lower bounds
on the time of gossiping, in both the worstcase and average aspects.
For the multipleaccess channel, we introduce a framework to study stability
of deterministic broadcasting protocols in adversarial settings. Stability means
that the number of packets in queues is bounded in any execution. We consider
natural classes of protocols and study stabilityrelated issues for the channels
with and without collision detection depending on the rates and burstiness of
injection of packets.
This abstract accurately represents the content of the candidates thesis. I rec
ommend its publication.
Signed
Bogdan S. Chlebus
DEDICATION
I would like to dedicate this work to my wife Joanna and son Mikolaj.
ACKNOWLEDGMENT
Thanks are due to my advisor Bogdan Chlebus for his guidance and inspiration.
This dissertation contains results obtained jointly with Bogdan Chlebus and
Dariusz Kowalski. I thank them for a rewarding and fruitful cooperation.
My interests in mathematics were developed at the time I was in high shod,
the 14th Liceum Ogolnoksztalcace imienia Stanislawa Staszica, in Warsaw,
Poland. I am especially grateful to Wojciech Boratynski, Jacek Jakubowski,
Jerzy Lisiewicz, Jacek Mical, Nina Tomaszewska for how they taught mathe
matics.
I greatly benefited from studying computer science at the Warsaw University, in
Warsaw, Poland. I thank my teachers of that time, Bogdan Chlebus, Krzysztof
Diks, Wlodzimierz Ogryczak and Andrzej Szalas for passing their passion for
algorithms to me.
During my Ph.D. studies at the University of Colorado at Denver and Health
Science Center, I enjoyed courses offered by the Department of Computer Sci
ence and Engineering and by the Department of Mathematics. I want to thank
the professors who taught them, in particular Gita Alaghband, Bogdan Chle
bus, Krzysztof Cios, Ellen Gethner, Mike Jacobson, Rich Lundgren and Tolya
Puhalskii.
I would like to thank my friends Lukasz Heldt, Leszek Gryz, Krzysztof Lichota ,
Jerzy Szczepkowski and Michal Welnicki from the Hydra Store Project for their
support. I am especially grateful to Cezary Dubnicki from the NEC Labora
tories, America, who showed so much understanding of my goals beyond the
project.
Thanks are due to Grazyna and Leszek Grzegorzewscy for their unwavering
support and for understanding of my later interests in computer science.
I thank my parents Helena and Stanislaw for their love and for encouraging my
early interests in mathematics.
CONTENTS
Figures ................................................................. x
Tables.................................................................. xi
Chapter
1. Introduction.......................................................... 1
1.1 Historical perspective and motivation.............................. 1
1.1.1 Multipleaccess channel ........................................... 2
1.1.2 Multihop networks................................................. 3
1.2 Structure of this document......................................... 4
2. Technical preliminaries............................................... 5
2.1 Introduction....................................................... 5
2.2 Multihop radio networks .......................................... 6
2.2.1 Model of radio network ............................................ 6
2.2.2 Communication problems............................................. 7
2.2.3 Communication protocols............................................ 8
2.2.4 Oblivious protocols................................................ 9
2.2.5 Families of sets.................................................. 10
2.2.6 Summary of settings............................................... 12
2.3 Multiple access channel........................................... 13
3. Previous research.................................................... 16
3.1 Broadcasting...................................................... 16
3.1.1 Centralized protocols............................................. 16
3.1.2 Distributed protocols............................................. 17
3.1.3 Average cost of broadcast......................................... 20
3.2 Gossiping......................................................... 20
3.2.1 Gossiping with combined messages.................................. 20
3.2.2 Gossiping with separate messages.................................. 23
3.2.3 Manytomany communication ....................................... 25
3.3 Wakeup........................................................... 25
3.4 Multiple access channel........................................... 27
3.4.1 Stochastic approach............................................... 27
3.4.2 Deterministic approach............................................ 28
vii
3.5 Adversarial queuing.............................................. 29
4. Asynchrony in multihop radio networks ............................ 31
4.1 Introduction..................................................... 31
4.2 Technical Preliminaries.......................................... 34
4.3 Protocol by enforcing dominance.................................. 38
4.4 Lower bounds..................................................... 42
4.4.1 Edge and node adversaries...................................... 42
4.4.2 Crash adversary ............................................... 44
4.5 Verifying correctness of protocols................................. 46
4.5.1 Correctness against edge adversary............................. 46
4.5.2 Correctness against crash adversary............................ 51
4.6 Computationally hard problems...................................... 52
4.6.1 Hard for edge adversary.......................................... 52
4.6.2 Hard for crash adversary ........................................ 54
4.6.3 Hard for node adversary.......................................... 55
5. Averagetime complexity of manytoall communication................. 62
5.1 Introduction....................................................... 62
5.2 Technical preliminaries............................................ 64
5.3 Gossiping with combined messages................................... 66
5.4 Communication m2a with combined messages........................... 71
5.5 Gossiping with separate messages................................... 75
5.6 Communication m2a with separate messages........................... 77
6. Lower bounds on gossiping.......................................... 85
6.1 Introduction....................................................... 85
6.2 Randomized oblivious gossiping..................................... 87
6.3 Leader election and gossiping with large labels.................... 90
6.4 Deterministic oblivious gossiping with separate messages........... 91
7. Adversarial queuing in multiple access channel..................... 93
7.1 Introduction....................................................... 93
7.2 Technical preliminaries ........................................... 95
7.3 Stability for injection rate one.................................. 100
7.3.1 Adaptive protocols.............................................. 100
7.3.2 Fullsensing protocols ......................................... 105
7.4 Universal stability .............................................. 108
7.5 Channel without collision detection............................... 110
7.5.1 Acknowledgementbased protocols ................................ 110
7.5.2 Fullsensing protocols ........................................... 115
7.6 Channel with collision detection.................................. 119
8. Conclusion ....................................................... 124
8.1 Closing remarks................................................... 124
8.1.1 Asynchrony in radio networks...................................... 124
8.1.2 Averagecase time complexity of m2a radio communication .... 124
8.1.3 Lower bounds on radio gossiping................................... 125
8.1.4 Multipleaccess channel .......................................... 126
8.2 Future work....................................................... 126
References............................................................ 129
IX
FIGURES
Figure
4.1 Comparison of node adversary with edge one ............ 37
4.2 Algorithm DinstanceDomination.......................... 40
4.3 Guards are not sufficient to provide broadcast......... 47
4.4 A procedure to verify if node can be blocked........... 48
4.5 Algorithm VerifyEdgeCorrect.......................... 50
4.6 Algorithm VerifyAgainstCrashes ...................... 51
5.1 Protocol GossipCombinedMessages; code for node v..... 68
5.2 Procedure M2ACombined(A;)............................. 72
5.3 Protocol M2ACombinedMessages......................... 73
5.4 Protocol GossipSeparateMessages; code for node v..... 76
5.5 Procedure M2 ASeparate (A;); the code for node v...... 79
5.6 Protocol M2ASeparateMessages......................... 80
6.1 Return graph........................................... 88
6.2 Doubly sink graph...................................... 91
x
TABLES
Table
3.1 Distributed broadcast for directed and symmetric networks.......... 18
3.2 Gossiping for directed networks and combined messages............. 22
3.3 Gossiping for symmetric networks and combined messages............ 23
3.4 Gossiping for symmetric networks and separate messages............ 25
3.5 Gossiping for directed networks and separate messages............. 25
1. Introduction
We investigate algorithmic aspects of communication protocols in multihop
packet radio networks and the multiple access channel. Radio networks model
wireless data communication with arbitrary topology of direct transmissions
when the bandwidth is limited to one wave frequency. A multipleaccess chan
nel is a system in which a transmission delivers the message to all nodes. Both
these types of networks share the property that multiple packets arriving simul
taneously at a node result in mutual interference, which prevents receiving the
messages successfully by any among the recipients.
The fundamental algorithmic goal for networks is to implement useful commu
nication tasks. We consider broadcasting and gossiping among such primitives.
The static broadcast problem is about a scenario in which one source node gen
erates input data that need to be disseminated among all the nodes. In the
dynamic broadcast problem, input data are continuously injected into the nodes
and next are disseminated. The gossip problem starts with all the nodes holding
their individual input data (called rumors), and the goal is for all the nodes to
learn all the rumors.
For multihop radio networks, we initiate an approach to study asynchrony.
We investigate the complexity of static broadcasting in such a setting. Specific
results on gossiping in multihop radio networks concern upper and lower bounds
on the time of gossiping, in both the worstcase and average aspects.
For the multipleaccess channel, we introduce a framework to study stability
of deterministic broadcasting protocols in adversarial settings. Stability means
that the number of packets in queues is bounded in any execution. We consider
natural classes of protocols and study stabilityrelated issues for the channels
with and without collision detection depending on the rates and burstiness of
injection of packets.
1.1 Historical perspective and motivation
The research on packet radio networks has been first done for the multipleaccess
channels, which are the same as singlehop networks. Only later the topic has
been extended to general multihop packet radio networks.
1
1.1.1 Multipleaccess channel
The inspiration to investigate singlehop radio networks came from the system
called Alohanet [1] developed at the University of Hawaii. The work on this
system started already at the end of the 1960s. This network was built to
provide means of communication between the main computer and its termi
nals located on remote islands. The system used electromagnetic waves as the
communicating medium. The constructors of this network did not consider this
medium to be really affecting their design, but rather their design of a broadcast
architecture created a fruitful approach to utilize a radio channel.
Subsequent work was motivated by the development of the system called Ether
net [69] in mid 1970s, which is used to this day as the most popular implemen
tation of localarea networks. Ethernet uses coaxial cable as the most popular
medium of communication in its implementations.
Traditional deterministic schemes like timedivision multiplexing are not effi
cient on the multipleaccess channel, since the stations attached to the channel
are usually idle for most of the time and the patterns of packet traffic are very
bursty. This makes protocols that arbitrate for access to the channel in a ran
domized fashion a natural choice. Historically the first such protocol was the
wellknown Aloha protocol, implemented in the Alohanet, in which the stations
attempt to transmit with a probability that is kept constant over time. Another
wellknown such a protocol is the truncated binary exponential backoff used in
Ethernet. Each message has up to 16 chances to be transmitted successfully.
After the zth failed chance to transmit, for i < 16, the time to wait before the
next transmission is chosen uniformly from the set p1"!101)], if aH attempted
transmissions fail, then the message is discarded. This protocol achieves low la
tency and few collisions under normal load and provides high channel utilization
under heavy loads.
Most of the research on the multiple access channel was concerned with develop
ing protocols that would provide a stable channel while maximizing throughput
in a scenario in which stations generate packets according to some regular dis
tribution, like Poisson one. Stability is defined to mean the ergodicity of the
associated Markov chain. See [16, 40] for surveys of this and related topics.
2
We study the stability of deterministic broadcast protocols on the multiple access
channel in an adversarial setting. An adversary generates packets according to
some constraints. An execution of the protocol can be interpreted as a game
between the adversary and the protocol. The protocol wins and the adversary
is defeated if the protocol guaranties bounded packet queues in any execution.
1.1.2 Multihop networks
In the work about algorithmic aspects of radio networks, the broadcast problem
has been most popular. This is for a number of reasons. One is that broadcast
is a fundamental communication primitive. Another is that it is natural to start
from a problem with a simplest specification and most wide range of applicability.
Least but not least, the additional factor was that even the problem of broadcast
provided a number of technical questions that have not been answered in a
completely satisfactory form to this day.
The achievability of broadcasting can be shown by a simple protocol called
RoundRobin, in which conflics are avoided by having single nodes transmit
in a cyclic way. One can show that n2 rounds are sufficient and necessary for
this protocol, in networks of n nodes.
This simple quadratic upper bound was the starting point of research on com
munication in multihop radio networks. The work on broadcasting in such radio
networks has been marked by three milestones.
First milestone: This direction of work was initiated in 1980s by Chlamtac and
Kutten [13]. They defined the model and considered sequential algorithms
to find efficient broadcast protocol for a given input network.
(This is how the model was born, in the context of centralized broadcast
protocols.)
Second milestone: The first distributed randomized broadcast protocols of sub
quadratic expectedtime performance were given by BarYehuda, Goldre
ich and Itai [8].
(The result was announced at a conference at the end of the 1980s.)
Third milestone: The first distributed deterministic explicit broadcast protocol
with subquadratic time performance was given by Chlebus, Gqsieniec,
Gibbons, Pelc and Rytter [17].
3
(The result was announced at a conference at the end of the 1990s.)
In Chapter 3 we review the recent relevant research about algorithmic aspects
of the communication problems in radio networks in greater detail.
This dissertation contains three specific topics of research on the multihop ra
dio networks. Two of them concern technical improvements on the previously
studied topics of gossiping in radio networks. Traditional approach to consider
radio networks assumes synchrony, at least on the level of local clocks ticking at
the same rate. One could even argue that synchrony is necessary to define the
model. We propose to consider asynchronous communication in radio networks
as one of the topics investigated in this dissertation. Our approach is by way of
suitable adversarial scenarios.
1.2 Structure of this document
The document is structured as three introductory Chapters numbered 1 to 3,
followed by four Chapters numbered 4 to 7 covering new results, and finally
Chapter 8 summarizing this work. Their contents are as follows.
In Chapter 2.1 we describe the model of radio network and multiple access
channel and explain the notions of communication protocol and communication
problem. This Chapter contains also a brief account of a historical perspective
of the direction of research given in Section 1.1.
Chapter 3 contains an overview of the most relevant previous results grouped
in sections corresponding to the most important communication tasks from the
perspective of this work. This includes communication problems for multihop
radio networks: broadcasting described in Section 3.1, gossiping described in
Section 3.2, wakeup presented in Section 3.3. Next we describe the most relevant
results on multiple access channel and adversarial queuing in Section 3.4 and 3.5
respectively.
Chapter 4 describes a certain novel approach to study asynchrony in radio net
works. Chapter 5 describes results on the average cost of gossiping in radio
networks. Chapter 6 presents three new lower bounds on gossiping in radio net
works, determined by a number of settings and classes of protocols. Chapter 7
proposes adversarial approach to study stability of communication protocols.
Chapter 8 summarizes our results and discusses possible venues of further work
in algorithmic aspects of radio communication.
4
2. Technical preliminaries
This section contains precise definition of the model of multihop radio network
and multiple access channel. We define communication goals for both systems
and describe tools used for developing protocols.
2.1 Introduction
Radio networks are a class of wireless packet communication networks in which
only one wave frequency is used for sending messages. The restricted bandwidth
results in conflict when different messages arrive simultaneously to a node. The
main challenge in developing communication protocols for such networks is to
address resolving collisions when conflicts for access to nodes occur among mes
sages.
One can distinguish two types of radio networks multiple access channel and
multihop radio networks. General multihop radio networks are modeled by
arbitrary directed graphs. Where directed edges represent transmissions range.
The multiple access channel also called singlehop radio network can be repre
sented by symmetric complete graph in which a node receives its own transmis
sion.
Most papers in the literature consider the case when nodes operate in perfect
lockstep, controlled by their local clocks ticking at the same rate. In one round, a
node can simultaneously transmit and receive messages, although some authors
define these modes of transmission to be mutually exclusive. The global clock is
defined to mean that local clocks show the same round numbers. In Chapter 4
we show a possible approach to define asynchrony in radio networks.
The communication goals for multiple access channel and multihop radio net
works are different. In case of multihop radio the goal is to minimize number of
rounds to complete a communication task. In case of multiple access channel we
assume that adversary injects packets in to the nodes. Each injected packet has
to successfully transmitted by its node. The goal is to develop stable protocol.
Stable protocol prevent packets queues from growing unbounded.
2.2 Multihop radio networks
5
In this section we define precise model of multihop radio network and notion of
the communication protocol. We also present tools used for developing protocols.
2.2.1 Model of radio network
Graph model. A radio network is modeled as graph G = (V, E), in which the
set of nodes V represent the physical nodes of the network and the set of edges E
represents the possibility of a direct transmission in the network. If node x of a
radio network can send a message directly to y, then node y is reachable from x.
For any ordered pair (u, v) of nodes in the network, edge u > v is in the graph G
if and only if node v is reachable from node u. When communication is in both
directions, which could be represented by the presence of both edges x > y and
y > x in the graph, then this is modeled by a simple undirected graph in which
the pair of nodes {x, y} is an edge.
The size of the newtork is defined to be the number of nodes V, which we
usually denote by n. The eccentricity, denoted by D, is the maximum length
of all shortest paths in the underlying graph. We assume that the size of the
network is known and may be a part of code of communication protocols.
Nodes of a network of size n are identified by their unique names. The most
popular scenario assumes that names give a onetoone correspondence between
the nodes and integers in the range [0, n 1]. This range of integers is often
denoted by [n].
Radio communication. When some two nodes transmit simultaneously at
a given round, and are both inneighbours of node x in the reachability graph
of the network, then a conflict occurs at x. A conflict at x results in all the
messages arriving to node x interfering with one another and each is received as
garbled. A message is said to be heard when it is received as fully readable in
its correct form. Radio networks have the following properties:
(a) If a node performs a transmission, then it transmits a single message.
(b) The message transmitted by a node is delivered in that round to all the
reachable nodes.
(c) A node can hear a message delivered at a round, if exactly one among its
inneighbours transmits in this round.
6
When no message is delivered to a node, then the node can receive only some
background noise. If a conflict results in an interference noise, which is distin
guishable from the background noise, then we say that the collision detection
mechanism is available. As opposed to multiple access channel sender cannot
verify if collision occurred at one of its outneigbours. We assume that collision
detection is not available, unless stated otherwise.
Rumors versus packets. Initially some nodes may hold their input contents
called rumors. When node i is initialized with a rumor, then this rumor is
denoted by r*. The goal of a communication protocol may be to disseminate
such input rumors.
The relative size of packets versus rumors affects the design of communication
protocols in the case of manytomany communication. There are two natural
scenarios. One, of combined messages, assumes that the whole current knowl
edge, about all the input rumor messages of the nodes in the network learnt so
far, can be placed in a single packet and transmitted between two nodes in just
one round. An alternative approach, of separate messages, stipulates that each
individual original rumor message has to be transmitted as a separate packet.
2.2.2 Communication problems
There are three most popular communication problems studied in literature:
broadcasting, gossiping and wakeup. The algorithmic task is to develop efficient
protocols to achieve the given communication goal.
In the problem of broadcasting, only one source node is assumed to hold an input
rumor and the goal is to make every node know the source rumor.
The problem of gossiping is about a scenario in which every node is initialized
with some input rumor, and the goal is to make all the nodes learn all the
rumors.
A generalization of gossiping called manytomany communication is about a
scenario in which some of the nodes have input rumors and the goal is to have
all these nodes get to know all the rumors, while all the nodes in the network
may participate in forwarding messages.
The problem of wakingup a network is about a scenario in which all the nodes
are initially asleep and some may become activated spontaneously. The goal is
7
to wake up all the nodes of the network. A sleeping node becomes active upon
hearing a message.
Basic underlying assumptions. To have a communication problem in radio
networks meaningful, we need to assume that the topology of the underlying
graph makes the communication task at hand possible to perform. In the case
of broadcasting, one assumes that all the nodes are reachable from the source
node. In the case of gossiping, one assumes that the graph is strongly connected.
In both the problems of broadcasting and gossiping we assume that nodes are
synchronized by a global clock. Our goal is to optimize the time of the protocol.
In the wakeup problem we assume that local clocks are ticking with the same
rate but awoken nodes do not know the global round number. A wakeup pro
tocol can be used to synchronize the local clocks at nodes.
2.2.3 Communication protocols
The work on communication and computer networks is concerned with studying
protocols for exchange of information among the nodes of the network. The goal
of protocols is to create an infrastructure for efficient implementation of this task.
This is achieved by nodes creating packets, which encapsulate the contents of
messages to be sent. A packet normally specifies at least the contents and often
lists specific recipients.
Communication protocols could be classified in a number of ways. The most
popular and natural categorizations distinguish (1) centralized protocols from
distributed ones, (2) deterministic protocols from randomized ones, and (3) ex
plicit protocols from existential ones.
A protocol is centralized, called also offline, when the network is given as an in
put to a sequential algorithm which finds the protocol. This means that different
networks run different incarnations of this protocol, as found by the sequential
algorithm.
A protocol is distributed, called also online, when its code is run concurrently
by all the nodes in the network, and the only difference in the code is the name
of the node. The initial knowledge of the nodes about the network in such a
scenario may be very limited, for instance, it may be limited only to the size n of
the network. Distributed protocols are typically adhoc, in the sense that nodes
do not rely on the knowledge of their neighbors.
8
A protocol is deterministic when it does not resort to a randomnumber gener
ator.
A protocol is randomized when nodes are allowed to use random numbers gen
erated in the course of an execution.
A protocol is explicit, also called constructive, when its code can be found in
time that is polynomial in the size of the network by a sequential algorithm.
A protocol is existential when the code uses combinatorial objects, with certain
required properties, that are only known to exist.
Complexity. One normally assumes that an execution of a communication
protocol is infinite. The time complexity of a deterministic protocol at hand is
defined to be the first round when the communication goal has been achieved.
The average time complexity of a deterministic communication protocol A on
directed networks of n nodes is defined to be the expected time complexity of A
on a random directed radio network of n nodes. Such a network has the property
that for any ordered pair {i,j) of nodes, for 0 < i, j < n, edge i j is in the
network with the probability 1/2, these events independent over all the pairs.
2.2.4 Oblivious protocols
The set of nodes performing transmissions at a round is called simply the trans
mission of this round. An execution of a communication protocols is a sequence
of sets of nodes (T0, Tj, T2,...}, where set Tj is the transmission for round i.
A protocol is oblivious if it is structured as follows.
1. There is a sequence of sets of nodes S = (So, Si, S2, ) Any node v can
compute if v Si based on the name of v and the size of the network n.
2. A node v may perform transmission at round i only if v Si. For a node
v 6 Si, the decision whether to participate in transmission for round 1 and
what are the contents of the transmitted message, depend only on the set
of input rumors known by v at round i.
Broadcast. An oblivious broadcast protocol is determined by a sequence of sets
of nodes S = (S0, Si, S2, }, where So is the singleton set containing only the
source. Node v E Si performs a transmission at round i if it has received the
9
source message by round i and the packet transmitted consists of the source
message.
Gossip. An oblivious gossip protocol for the model of combined messages is
determined by a sequence of sets of nodes S = (So, Si, S2) ) Node v G Si al
ways performs a transmission at round i, with the packet transmitted containing
all the input rumors learned by node v by round i.
An oblivious gossip protocol for the model of separate messages is also deter
mined by a sequence of sets of nodes S = (So, Si, S2, ) Node v Â£ Si always
performs a transmission at round i. The packet transmitted at a round contains
a single input rumors learned by node v by round i; the rule to select an input
rumor to place in the packet transmitted at a round is an additional component
of the protocol.
There is a particularly simple oblivious protocol called RoundRobin. Set Si
consists of the singleton node named x for which the congruence x = i (mod n)
holds true. In the case of broadcasting, this protocol has the property that after
at most n2 transmissions every node knows the source message.
2.2.5 Families of sets
Oblivious communication protocols in radio networks often are structured in a
way that can be interpreted in combinatorial terms.
We use the notion of selection by intersection to mean distinguishing a single
element of a set as the only element of some other set. For a given a subset
A C X of a finite domain X, element z A is selected by a set B C X when
ACi B = {z}.
Selective families. A family S of subsets of X is called kselective if we can
select an element from any subset A C A of size A < k by a set in S. A
family S of subsets of X is called strongly kselective, if we can select every
element from any subset A C X of size A < k by a set in S.
When \X\ = n, then such a families is called (n,k)selective, or (n, k)strongly
selective, respectively.
The notion of a (n, /c)selective family can be defined explicitly as
F = {F0, Fi,..., Fm} where Fj C [n] and for each S C [n], where l^l < k, there
exists Fi E Fk such that Fj fi S\ = 1. The number m is the size of the family.
10
Similarly, the notion of a (n, k)strongly selective family can be defined as T =
{F0, Fi,..., Fm} where Fj C [n] and for each S C [n], where \S\ = k, and each
v 5, there exists Fj F such that Fj fl F = {u}.
Let n, k and r be positive integers so that r < k < n. Let S be a family of
subsets of [n]. We say that S is an (n,k,r)selector if, for each set A C [n] of
size  A  = k, there are at least r elements in A that can be selected from A by
sets in S.
Observe that (n, /c)selective families are (n, k, l)selectors in selector termi
nology. Similarly, (n, &)stronglyselective families are nothing but (n, k, k)
selectors.
When the indegree of a network is at most A, then one can use (n, A)selective
family of size m to complete broadcast in time nm.
Selective families were defined by Chlebus, Gqsieniec, Gibbons, Pelc and Ryt
ter [17], who used them in their deterministic subquadratic broadcast proto
col. Stronglyselective families were considered first by Clementi, Monti and
Silvestri [34]. The name selector was introduced by De Bonis, Gqsieniec and
Vaccaro [36], who defined selectors is in terms of binary matrices with the cor
responding properties. The definition we use follows Chlebus and Kowalski [23],
who gave best known explicit selectors.
Synchronizers. Wakeup protocols use combinatorial objects that are gener
alizations of selective families. They are usually defined as binary matrices, in
which columns represent characteristic vectors of sets.
An (n, k)synchronizer of length m is an n x m matrix where the ith row is
a schedule of transmissions for Ah node and m is time of the protocol. The
matrix has the property that for any wake up schedule and any subset of at
most k nodes there exists round i < m in which only one node transmits.
An (n, g)universal synchronizer is set of n binary vectors where the zth vector
is a schedule of the Ah node. The set of vectors satisfies the following property:
for any subset k vectors and any wake up schedule there exists round i < g(n, k)
such that only one node transmits.
Radio synchronizers were defined by Chrobak, Gqsieniec and Kowalski [30] in
their solution to waking up a multihop radio network. This notion was already
implicitly used by Gqsieniec, Pelc and Peleg [45] in their algorithms for waking
11
up a multipleaccess channel. Universal radio synchronizers were defined by
Chlebus and Kowalski [13] as a tool to improve the time of wakeup.
2.2.6 Summary of settings
We study communication problems and protocols in a number of settings. In
this Section we summarize the most relevant ones. The Section is a place of
reference for the reader.
Symmetry of edges: Edge x > y in the underlying graph means that a trans
mission at x results in a message delivered to y. When communication
is in both directions, which could be represented by the presence of both
edges x > y and y > x in the graph, then this is modeled by a simple
undirected graph in which the pair of nodes {x, y} is an edge.
Knowledge of topology: Dynamic mobile networks may change topology. It is
useful to have distributed communication protocols that do not rely on
the nodes to know the current topology. It is natural to classify protocols
by the level of knowledge they expect from the nodes, but often it is the
networks that are categorized by this knowledge, which is to mean the
same. The most important case occurs when nodes are not expected to
know even their neighbors. Then such networks are called adhoc. The
next degree of knowledge of topology is when nodes know only their neigh
bors: such networks are referred to as with knowledge of neighbors or with
known neighbors.
Collision detection: When no message is delivered to a node, then the node can
receive just some background noise. When at least two messages are deliv
ered, then they cannot be received due to conflict. If a conflict results in
an interference noise, which is distinguishable from the background noise,
then we have say that the collision detection mechanism is available. A
node that receives the interferencenode signal is also said to hear collision.
Range of identification numbers: Nodes have and know their unique identification
numbers, called simply names. The strongest assumption in that respect
is to have names in the range {0,1,..., n 1} = [n]; we refer to this as
compact names. Another common setting is specified by assuming that
unique names are in some range [0,/(n)], where f(x) is a polynomial in
x; we refer to this as (polynomially) sparse names.
12
Size of packets: A node transmits some portion of information during one round.
In the case of broadcasting, the source message is assumed to be sufficiently
small to allow to be transmitted just in one round. For gossiping, there
are two possible scenarios. First approach, of combined messages, assumes
that the whole current knowledge, about all the messages learnt so far,
can be transmitted between two nodes in just one round. An alternative
approach, of separate messages, stipulates that each individual original
input rumor/message has to be transmitted separately.
Synchrony: In broadcasting and gossiping we assume that local clocks are glob
ally synchronized in that they indicate the same round number. In the
case of the wakeup problem we assume only that local clocks are ticking
at the same rate and each node knows only its private round number. A
wakeup protocol can be used to synchronize all these local clocks.
2.3 Multiple access channel
Multiple accesses channel is represented as set of nodes (stations) V connected
to the common channel. The best practical example of multiple access channel
is Ethernet. Number of stations is denoted by Vj = n. We assume that station
have unique names from range [n]. Nodes operate in perfect lock steps called
rounds. Each node stores queue of packets to be transmitted. Only one packet
can be successfully transmitted per round. Each successfully transmitted packet
leaves its queue. Packet transmitted in a round reaches all nodes in the same
round including its sender. If there is exactly one node transmitting in a round
then all nodes hear (successfully receive) the transmission. If there are at least
two nodes transmitting in the same round then collision occurs. Communication
channel can be equipped with collision detection mechanism. On the channel
with collision detection nodes can distinguish between collision and silence. If
no collision detection mechanism is provided then collision is treated as silence.
We can observe that sender of the message can verify if collision occurred even
if no detection mechanism is provided. This is because sender hears its own
transmission in case of success otherwise it hears nothing.
Most research on multiple access channel considers stochastic model. In stochas
tic model one assumes that packets are generated with some fixed distribution
e.g. new packet can be generated in round t with constant probability p < 1 in
each node independently. Each station runs its own incarnation of the protocol
13
V. In each round protocol V decides about nodss transmission. The goal is
to design stable protocol that is protocol for which associated Markov chain is
ergodic. Ergodic Markov chain guaranties that during infinite execution system
will reach a state in which queue size is zero with very high probability.
Inspired by stochastic model and adversarial queuing theory we show how to
define deterministic adversary generating packets. Adversary of type (A, w) is
defined by two parameters injection rate A < 1 and size of the window w.
Window w is defined as any sequence of w consecutive rounds. In each window
of size w adversary can inject at most Aw packets. Such defined adversary
models to some extend real burstiness of traffic. We can see that adversary can
inject up to Aw in single round. Parameter Aw is called burstiness. Our goal is
to develop stable protocol that is protocol which prevents packets queues from
growing unbounded in infinite execution. To make this task visible we have to
assume that injection rate is at most one A < 1 otherwise there can be infinitely
many packets in the system. We can distinguish three classes of protocols:
Acknowledgementbased, protocol. This is the weakest class of protocols.
Nodes cannot access global round number. Local time is available for
active stations. Empty node is activated by injection of the new packet.
Station having transmitted all its packets becomes idle. Local time is
counted as follows. For active station local round number t denotes number
of rounds since the last its successful transmission that was heard on the
channel. If no such transmission then t denotes number of rounds since
node activation time. Station decides about transmission based on local
round number t, number of nodes n, name of the station.
Fullsensing protocol. Nodes can access global round number. In round
t each node makes decision about transmission based on: global round
number, number of nodes n, size of the queue and the history of the
channel during previous t 1 rounds.
Adaptive protocol. This is the strongest class of protocol. Adaptive proto
col is an extension of fullsensing protocol. Additionally station can attach
some information to the transmitting packets e.g. station can attach in
formation about its queue size.
Basic quality of protocols is to have each packet eventually heard on the channel.
This property is called fairness. Our goal is to guarantee stability and fairness of
14
the protocol. Notion of stable protocol is extended to universally stable protocol.
Protocol V is universally stable if it is stably for any injection rate A < 1 and
arbitrary window size w. We also consider stronger class of protocols called
strongly stable protocols. Protocol is strongly stable if queue size is proportional
to the burstiness Xw.
15
3. Previous research
This Chapter contains an overview of the relevant results about algorithmic
aspects of communication problems in multihop radio networks, multiple access
channel and adversarial queuing. In case of multihop radio networks we review
results for broadcasting, gossiping and wakeup.
3.1 Broadcasting
In the broadcast problem, there is one distinguished node s called the source,
which contains an input message/rumor that needs to be disseminated to all the
other nodes.
We assume that each node v knows the size of the network n and its name in
[n\. Additionally we assume perfect synchrony, so that global round numbers
are available to all the nodes. A broadcast protocol is defined as a sequence of
transmissions {T0, T\,..., Tk)...), where T* C [n]. In round i, all nodes from T{
that have learnt the source rumor by then transmit. We say that a broadcast
protocol completes broadcasting at a round, when this is the first round by
which all the nodes in the network know the source rumor message. The goal
in designing broadcast protocols is first to minimize the time complexity to
achieve this communication task, and also to propose protocols that are explicit
and easy to implement. The most efficient protocols known in the literature are
existential only.
3.1.1 Centralized protocols
In the offline approach we assume that first some global instance finds a broad
cast protocols for the given radio network G = (V, E) and source s. Next the
protocol is delivered to each node. Nodes follow the protocol to broadcast the
message.
Chlamtac and Kutten [13] showed that computing optimal protocol is NP
complete. This holds true even for planar graphs, which was shown by Sen
and Huson [73]. Alon, BarNoy, Linial and Peleg [3] showed that there exists
16
bipartite graph G of n nodes that requires time fl(log2n). The proof was exis
tential and did not provide construction of the graph. Chlamtac and Weinstein
[3] presented approximation algorithm that for each n node bipartite graph finds
an explicit protocol of time complexity (9 (log2 n). This protocol can be used for
directed networks to disseminate message in time 0(Dlog2 n). For symmet
ric networks, Gaber and Mansour [39] presented algorithm which computes a
broadcast protocol of time complexity 0(D + log6). This result was improved
by Kowalski and Pelc [64]; the authors presented explicit broadcast protocols
of time complexity 0(D + log2n). This protocol is optimal since D is natural
lower bound for the broadcast problem and we know that there exists bipartite
graph of n nodes that requires f2(log2n). Elkin and Kortsarz [37] showed that
radio broadcast cannot be approximated in polynomial time with factor fi(logn)
unless NP C BPTIME{n^l^).
3.1.2 Distributed protocols
Directed networks. In on line settings we assume that there is a directed
path from source s to each node in the network. We do not assume any
thing about other paths. Additionally, each node knows n the total number
of nodes in the network and its name. The topology of the network is unknown.
BarYehuda, Goldreich, and Itai [8] presented first randomized broadcast pro
tocol for unknown networks. The expected time of the broadcast protocol was
0(2} log n + log2n) for any nnode network with diameter D. This result is
almost optimal. Kushilevitz and Mansour [66] showed that for any randomized
broadcast protocol there exists nnode network with diameter D that requires ex
pected time 0(2} log(n/2})). Czumaj and Rytter [35] and independently Kowal
ski and Pelc [62] presented randomized broadcast protocol of expected time
0(D\og(n/D) + log2n). Thus all the problems regarding the optimum time
complexity of randomized broadcast appear to be solved.
In deterministic approach, one can observe that each node decides about trans
missions based on messages it received before (history), global round number,
name and n. Since the network is directed, return paths may not exist. This is
the reason for which the broadcast protocols for directed networks studied in the
literature have been all oblivious. That is each node decides when to transmit
based on n, name and round number. Oblivious broadcast protocol can be also
defined as sequence of transmissions BP = (To, T2, ..., 7*,), where T C [n] is
computed prior to the start of an execution. The simplest oblivious broadcast
17
deterministic protocol randomized protocol
directed network 0(n log2 D) 0(D\og(%) + log2n)
ft(n\og D) fi(Â£Mog(g))
symmetric network 0(n) 0(I>log(g) + log2n)
f2(n) tt(D)
Table 3.1: Distributed broadcast for directed and symmetric net
works. Protocols are adaptive in the case of symmetric networks
and oblivious in the case of directed networks.
protocol called RoundRobin avoids collisions altogether. In round number i
node whose name is equal to i mod n transmits. We can see that this proto
col in the worst case requires D(n2) rounds. The first deterministic broadcast
protocol that works faster was presented by Chlebus, Gqsieniec, Gibbons, Pelc,
and Rytter [17]. Their broadcast protocol worked in time 0(nll//6) for any n
node network. Next this result was improved to 0(n3^2) by Chlebus, Gqsieniec,
Ostlin, and Robson [20]. Chrobak, Gqsieniec, and Rytter [31] showed that there
exists broadcast protocol of time complexity 0(n log2 n) for any nnode network.
This broadcast protocol works also when names are in [nc] where c is some
constant. The authors in their broadcast protocol used special combinatorial
objects. A kselector is defined to be a sequence Fk = {Po, Pj, > Fm} where
Fi C [n] and for each pair of disjoint sets X,Y C [n], such that f < Xj < k
and T < k, there exists Fi Â£ Fk such that Pi Â£1X1 = 1 and Fi n Y\ =0.
The existence of a kselector with required size m < k log n was proved by the
probabilistic method. Next Czumaj and Rytter [35] improved this result and
showed the existence of of time nlog2 D. This protocol also relies on fcselectors.
Explicit /cselectors of approximately good size were given by Indyk [55]. This
allowed to achieve the best known explicit broadcast protocol of time complexity
0(nlog3n), see [55].
Clementi, Monti and Silvestri [34] showed that for each broadcast protocol there
exists network that requires time fl(n log D). This almost matches the best
known upper bound.
18
See Table 3.1 for a summary of the best known upper and lower bounds.
Symmetric networks. In symmetric networks broadcast is much more com
plex since nodes can use their history of received messages to compute schedule.
The simplest adaptive broadcast protocol works in the following way. Source
node s initiates token containing the message. Token traverses the network in
DFS manner. We assume that each node knows its neighbors if not one round
of Round Robin fixes it.
Node that owns token transmits it to one of its not visited neighbors. The
recipients name is attached to the token. This allows each neighbor verify who
is the recipient of the token and learn which node is being visited. The time of
this protocol is 0(n). We can see that protocol is adaptive that is node transmit
based on the messages received before.
This protocol uses also spontaneous transmitions that is transmitions that do
not contain the broadcasted message. The purpose of spontaneous transmitions
is to pass some information about graph structure. In case of DFS protocol
nodes learn their neighborhoods with spontaneous transmitions. This broadcast
protocol is optimal in case D = Q(n).
Surprisingly this broadcast protocol is also optimal for networks with constant
diameter. Kowalski and Pelc [65] for given adaptive broadcast protocol con
structed symmetric network of diameter 3 so that broadcast protocol requires
fl(n) rounds. Similar result was claimed by BarYehuda, Goldreich, and Itai
[8]. Unfortunately the presented proof is correct only for oblivious protocols.
Kowalski and Pelc [62] also introduced following realistic model of the broad
cast. They assume that all nodes are asleep but source. More precisely nodes
do not realize that a broadcast protocol is being executed until they receives
broadcasted message. Source initiates broadcast. Each node that receives mes
sage is woken up and joins executing the broadcast protocol in a synchronous
manner. We can see that DFS protocol in such model does not work since nodes
cannot learn their neighbors before the broadcast protocol starts. In such model
authors showed that for each broadcast protocol there exists network which
requires time D(nlogn/log(n/D)). The authors presented broadcast protocol
which takes 0(nlogn) rounds. In the same model when each node addition
ally knows its neighbors, Kowalski and Pelc [63] showed that for each broadcast
protocol there exists network of constant diameter which requires fThe
authors also presented broadcast protocol which requires subliniar time o(n) on
19
any nnode graph with diameter o(loglogn).
3.1.3 Average cost of broadcast
Elsasser and Gqsieniec [38] considered the average complexity of broadcast. This
is the same as studying the expected time of broadcasting in random graphs.
The random graph is obtained by putting edges between each pair of nodes with
probability 1/2. The goal is to design a broadcast protocol which achieves the
best average time for given p. The authors considered offline and oblivious on
line protocols. In case of offline protocols authors proposed a broadcast protocol
which requires expected time 0( + In d) where d = pn is average degree of
node. In case of oblivious online protocols authors proposed oblivious broadcast
protocol which requires 0(lnn). The authors proved that both protocols work
in optimal average time. Moreover the average cost of oblivious online and
offline are the same C>(log n).
3.2 Gossiping
The problem of gossiping is a natural communication problem in which all nodes
want to broadcast their rumor messages concurrently. We assume that the global
clock is available. Each node knows its name and the size n of the network.
Gossiping can be categorized by the setting and restrictions on protocols. Proto
cols may be oblivious or adaptive. Another property of protocols is to be either
distributed or centralized. Networks may be directed or symmetric. The relative
size of packets and input rumors may determine either the case of separate or
combined messages.
3.2.1 Gossiping with combined messages
A gossiping protocol can be defined as a sequence (T0, Ti,..., Tk) where Tt C [n\.
In round number i all nodes that belong to Tj transmit their all messages learnt
so far.
Centralized protocols. In symmetric networks there is very natural lower
bound n. Each nnode star requires exactly n rounds. Gqsieniec, Potapov,
and Xin [48] presented algorithm that computes in polynomial time a gossiping
protocol of time complexity exactly n for each symmetric networks. For each
directed network one can find a gossiping protocol that works in time 2n. In this
20
construction one distinguished node is the root e.g. 1. We build intree from
root and outtree. First all messages are collected by root with intree. Next
root broadcast all messages with outtree. This idea was first used by Xu [74].
Distributed protocols in symmetric networks. The lower bound n holds
because of the star. The simplest adaptive gossiping protocol works in time
0(n). One distinguished node called leader issues a token. Token traverses
graph in DFS manner. Each node having received a token attaches its message
and forwards it further.
When DFS is completed leader owns a token with all the massages. Second
DFS traversal broadcasts all messages. We can see that DFS protocol requires
a leader that issues the token. In case the names are in [n], all nodes can accept
vertex with name 1.
The problem of leader election becomes more complex when names are in [nc]
where c is constant. We can see that if leader is elected and nodes know their
neighborhoods gossiping can be completed in 0(n) rounds. Chrobak, Gqsieniec,
and Rytter [31] presented leader election protocol that works in time 0(n log3 n)
when names are in [nc]. The idea of this protocol is to learn each node the
largest label bit by bit. Protocol works in logn rounds. One round is to learn
one bit of the largest label. Initially all nodes are candidates to own the largest
label. In zth round all candidates with zth bit equal 1 broadcast it. We can
use the broadcast protocol because all candidates broadcast the same message
1. If a node receives message in zth round it knows that zth bit of the largest
label is 1 otherwise it is 0. Node stops to be a candidate in zth round when it
contains 0 on the zth position and it receives message 1. This is information
to the node that there exists some larger label. After logn round each node
knows the largest label. If we use the fastest known broadcast protocol given
in [31], which takes 0{n log2 n) rounds, the leader can be elected in 0(nlog3n)
rounds. This protocol works also in directed networks. In case nodes do not
know their neighborhoods leader election is not enough. Gqsieniec, Pagourtzis,
and Potapov [44] presented a gossiping protocol that takes time 0(n log3 n) in
case nodes do not know their neighborhoods.
Distributed protocols in directed networks. We can observe that simple
oblivious RoundRobin algorithm completes gossiping in time 0{n2) for any n
node directed graph. First deterministic protocol that was faster was presented
by Chrobak, Gqsieniec, and Rytter [31]. The authors presented an adaptive
21
adaptive oblivious
deterministic protocol (9(n4//3log4n), fi(n) 0(n2), Q(n2)
randomized protocol 0(nlog2n), f2(n) 0(n2), fl(n)
Table 3.2: Gossiping for directed networks and combined mes
sages.
gossiping protocol that works in time 0(n3^2 log2 n). The idea underlying the
gossiping protocol is to execute y/n rounds of RoundRobin. Next the node
that owns the most messages broadcasts them to all other nodes with broadcast
protocol. This round is repeated until all messages are disseminated. Next this
result was improved to 0(n(y/D + log2n)) by Xu [74], This adaptive gossiping
protocol uses the following idea. One distinguished node called root builds the
picture of the unknown graph. First nodes execute y/n rounds of ROUND
Robin. Next protocol takes y/n phases. Each phase takes 0(n) rounds. In
phase K root discovers nodes that are K \/~D indistant. This protocol works
only when names are in [nj. The fastest known gossiping protocol was proposed
by Gqsieniec, Radzik, and Xin [49] works in time 0(n4/3 log4 n). This protocol
works even when names are in [nc\. The best randomized protocol operates
in the expected time 0(nlog2n), it was given by Czumaj and Rytter [35]. It
is an improvement over the algorithm of time 0(n\og3n) given by Liu and
Prabhakaran [67]. The best known lower bound for adaptive gossiping protocol
is n because of the nnode star. The lower bound for broadcast Q(n logn) shown
by Clementi, Monti and Silvestri [34] works only for oblivious gossiping protocols.
Clementi, Monti and Silvestri [34] showed interesting approach to gossiping. The
authors presented gossiping protocol that takes time (9(nA2logn) where A is
the maximum indegree. We can see that for A = O(yfn) the protocol achieves
time (D(n3/2).
See Table 3.2 for a summary of the best known upper and lower bounds.
Oblivious protocols. An oblivious gossiping protocol can be defined as a se
quence of transmissions (T0, T\,..., T*.) where each Tj C [n] is computed prior to
the execution. In round % nodes that belong to set Tt transmit its all knowledge.
Since protocol is oblivious each node computes its transmissions time based on n,
22
adaptive oblivious
deterministic protocol C?(n), fi(n) 0(n3/2), G(n3/2)
randomized protocol 0{n), fi(n) 0(nlog2 n), Q(n)
Table 3.3: Gossiping for symmetric networks and combined mes
sages.
name and the round number. The model of oblivious gossiping was introduced
by Chlebus, Gqsieniec, Lingas, and Pagourtzis [19]. For given oblivious gossip
ing protocol authors constructed directed network which requires time H(n2).
Thus RoundRobin is optimal for directed networks. In case of symmetric
networks authors presented a oblivious gossiping protocol that works in time
0(n3/2). This is an optimal protocol as shown by Pelc and Kowalski [65]. A
randomized oblivious gossiping protocol is a protocol in which the probability
of transmissions for each node depends only on round number and the name.
We can see that a deterministic oblivious gossiping protocol is a special case of
randomized oblivious gossiping protocols. In [19] the authors presented a ran
domized oblivious gossiping protocol that works in expected time 0(nlog2n)
for symmetric networks and in time 0(min {m, DA} log2n) for directed net
works. We can see that in case of symmetric networks randomization provides
significant improvement from 0(n3/2) to 0(nlog2n).
See Tables 3.2 and 3.3 for summaries of the best known upper and lower bounds.
3.2.2 Gossiping with separate messages
In model of separate messages we assume that the size of the transmitted mes
sage is limited to 0(\ogn). This model was considered by BarYehuda, Israeli
and Itai [9] and Clementi, Monti and Silvestri [34], In first case authors pre
sented randomized oblivious protocol to broadcast k messages from source s in
time Oik + nlog2n). In second case authors presented oblivious deterministic
protocol to broadcast k messages from source s in time 0((k + D)n).
Gossiping with separate messages is defied similarly to the one with combined
messages. Each node contains small message of size O(logn) and all nodes
want to broadcast their messages parallely. We call this problem 1gossiping.
23
The mgossiping is an extension of 1gossiping in which nodes can combine up
to m messages. The ngossiping correspond to the gossiping with combined
messages. The gossiping protocol with separate messages is defined as BGP =
(T0,Ti,... ,Tk) where T, C [n]. In round number i all nodes from T, transmit.
Additional component of this protocol is procedure choosing which message
should be transmitted. We can modify RoundRobin so that it executes 1
gossiping. We apply D + n rounds of RoundRobin with procedure choosing a
message to be transmitted defined by FIFO. We will call this oblivious protocol
BoundedRoundRobin. BoundedRoundRobin completes gossiping in
time 2n2.
Centralized protocols. Gqsieniec and Potapov [47] considered offline 1
gossiping. The authors constructed directed network which requires fi(n2)
rounds for any BGP. Thus offline and on line 1gossiping for directed graphs
in closed since the BoundedRoundRobin works in 0{n2). For symmetric
graphs authors proposed offline BGP that works in time (9(nlog2 n). This pro
tocol is almost optimal since authors showed that there must exist network of
constant diameter which requires fl(nlogn) time.
Distributed protocols. Christersson, Gqsieniec, and Lingas [29] considered
on line BGP. The authors presented adaptive BGP for directed networks that
works in time 0{v?!2 log3 n) for y/ngossiping. We can see that upper bound for
y/ngossiping is very close to the upper bound of ngossiping. For symmetric
graphs authors proposed adaptive BGP with time 0{v?!2 logn). The idea of
this protocol is to build BFS tree in time 0(n3/2) with the oblivious protocol
presented in [29]. Next root of the BFS tree learns up to n3^2 edges and all n
messages. Root computes schedule of transmissions for each BFS layer based
on the edges it knows. The computed schedule of broadcasts guarantees that
single message traverses each BFS level in time 0(y/n log n). Thus we can use
pipelining in which separation between messages is Q(^/nlogn) rounds.
The authors also showed how to use collision detection mechanism to complete
1gossiping in symmetric networks in time nlogn. It was the first paper in
which the collision detection mechanism was used to speed up the protocol. The
authors also adapted oblivious randomized BGP provided by R. BarYehuda, A.
Israeli, and A. Itai [9] to complete 1gossip for symmetric networks in expected
time 0(n + n log2 n).
See Tables 3.4 and 3.5 for summaries of the best known upper and lower bounds.
24
adaptive oblivious
deterministic protocol 0(n3//2), Q(nlogn) 0(n2), f}(n)
randomized protocol 0(n\og2n), fl(n) 0(nlog2 n), fl(n)
Table 3.4: Gossiping for symmetric networks and separate mes
sages.
adaptive oblivious
deterministic protocol 0(n2), Q(n2) 0(n2), 0(n2)
randandomized protocol 0(n2), fl(n2) 0(n2), VL(n2)
Table 3.5: Gossiping for directed networks and separate mes
sages.
3.2.3 Manytomany communication
Gossiping can be generalized to manytomany communication. Gqsieniec,
Kranakis, Pelc, and Xin [43] considered the problem defined as follows. There
is set S of S = k nodes that want to disseminate their messages to each other.
The maximum distance between any two nodes from S is d. The goal is to design
fast multicast protocol. In [43] authors considered following model. Network is
symmetric. Each node knows topology of the network but does not know the set
S. In such model authors presented a protocol that requires 0(d log2 n+k log3 n)
rounds.
3.3 Wakeup
The wake up problem is about initializing the network in a scenario when all
the nodes are initially asleep. Again, number n denotes the size of the network.
Names of nodes are in interval [nc]. The network topology is not assumed to be
known by the nodes.
A node can wake up spontaneously or can be woken up by hearing a message.
The times of spontaneous wakeups are not restricted in any way. The goal is to
25
design a protocol which eventually wakes up all the nodes. Wakeup protocols
are parametrized by the size n of networks. The quality of a wakeup protocol
is measured by its time complexity.
Each node knows its local time according to its private clock. No global synchro
nization of local clocks is assumed. We start measuring the global time from
round 0 when the first node wakes up. Each node v having woken up starts
executing its instance of the wakeup protocol based on its name and the local
clock.
Initially wake up problem was studied in single hop networks (complete graphs).
Gqsieniec, Pelc, and Peleg [45] presented a deterministic protocol that required
0(n2 log n) rounds in a nnode single hop networks. Jurdzihski and Stachowiak
[57] presented a randomized Monte Carlo protocol which errors with probability
0 < e < 1 and requires 0(lognlog(l/e)) rounds. Indyk [55] presented algorithm
which finds a protocol of time C?(n1+), for any e > 0. The algorithm requires a
quasipolynomial time C,(2polylog n)
Chrobak, Gqsieniec, and Kowalski [30] were the first to study wakeup for multi
hop radio networks. Their protocol was existential and required 0(n5/,3logn)
rounds. This paper introduced the notion of a synchronizer and showed the exis
tence of (n, ^synchronizers of length k2 log n by the probabilistic method. The
same authors showed how wake up protocol can be applied with logarithmic fac
tor overhead to leader election and time synchronization problem. Next Chlebus
and Kowalski [22] showed existence of wakeup protocol for multihop networks
which works in 0(n3//2 logn) rounds. The authors extended the notion of (n, k)
synchronizers to (n, g)universal synchronizers. The authors proved existence of
universal synchronizers with function g(n,k) that is 0(kmin{k, y/n}\ogn) and
used such synchronizers in wakeup protocols. The fastest known existential
wakeup protocol works in time 0(n log2 n) as shown by Chlebus, Gqsieniec,
Kowalski, and Radzik [18]. The authors showed existence better (n, g)universal
synchronizers with function g(n,k) = 0(k log k log n) and used it in the pro
tocol. The same authors also showed the best known explicit protocol which
works in time (nApolylog n). The best known lower bound is the same like
for broadcast Q.(n\ogD) [34] since broadcast is special case of wake up.
A wake up protocol can be used to elect leader and synchronize local clocks. Let
us assume that wake up protocol works in time T(n) and each name is in [nc].
The idea of leader election is to learn each node the largest label bit by bit. First
26
network is woken up to achieve partial synchronization. Next the largest label is
constructed in 0(\ogn) rounds following way. Initially all nodes are candidates
to be a leader. In zth round each candidate whose labels zth bit is 1 broadcast
it with wake up protocol. Nodes which receive wake up signal know that some
candidates zth bit equal 1. No signal means that zth bit of all candidates is
0. Node stops to be candidate when it receives 1 signal and its zth bit is 0.
After last round all nodes learn the largest name in the network. The leader
election process requires 0{T{n) logzz) rounds. When leader is elected it can
broadcast its local time with some broadcast protocol. Thus process of network
synchronization requires 0(T(n) log rz + b(n)) rounds where b(n) is the cost of
broadcast protocol e.g. 0(nlog2n) presented in [31].
3.4 Multiple access channel
We can distinguish two main approaches to multiple access channel stochastic
and deterministic. In the following sections we will cover previous results for
both models. Next we describe the previous results for adversarial queuing.
3.4.1 Stochastic approach
In stochastic approach one assumes that packets are generated with some dis
tribution. The most popular distribution is Poisson one with mean A. The goal
is to design protocol which is stable. Stability in the strongest form means that
the protocol returns to the state in which queues are empty with probability 1.
The quality of the protocol can be also measure in terms of average throughput
of the protocol called capacity. Stable protocol should provide capacity equal to
the average arrival rate A.
The most popular protocol used in Ethernet is binary exponential backoff protocol
see [69]. Each packet has limited number k = 16 of chances to be transmitted.
In zth attempt packet is transmitted with probability A. If all k attempts fail
then packet is discarded. This protocol belongs to the class of protocols called
backoff protocols. Backoff protocol can be described as sequence of probabilities
(po,Pi,...) in zth attempt packet is transmitted with probability pi. Goldberg,
MacKenzie, Paterson and Srinivasan [51] showed that there does not exist stable
backoff protocol for A > 0.42. Authors also consider class of stronger protocols
called fullsensing. Fullsensing protocol can additionally use the history of the
channel to decide about transmission. Fullsensing protocols are shown to be
unstable for rate A > 0.53.
i
27
Recent work includes the papers of Goldberg, Jerrum, Kannan and Paterson [50],
Goldberg, MacKenzie, Paterson and Srinivasan [51], Hastad, Leighton and Ro
goff [54], and Raghavan and Upfal [72]. See [40] for an overview of early work.
3.4.2 Deterministic approach
Broadcasting in a static case concerns a scenario in which some stations hold
packets at the beginning of an execution and the goal is to transmit either at
least on of them, which is the case in the selection problem, or all of them in
the allbroadcast problem, in both cases as quickly as possible.
Kushilevitz and Mansour [66] proved a lower bound fl(logn) for the selection
problem on the channel with n stations if collision detection is not available.
Willard [76] developed protocols solving the selection problem in the expected
time O (log log n) in the channel with collision detection. This demonstrates
that there is an exponential gap between the models with collision detection
and without it, with respect to the selection problem.
The allbroadcast problem was studied by Greenberg and Winograd [53] on the
channel with collision detection. In [53] authors show lower bound log
on allbroadcast problem when k stations contain packets to be transmitted.
Capetanakis [12] gave almost optimal adaptive protocol working in time 0(k +
k log ). Komlos and Greenberg [60] showed by counting argument existence of
the oblivious protocol which work on channel without collision detection in time
0(k log). This is optimal due to the lower bound fl(k log j) on the size of
^selective family showed by Clementi, Monti and Silvestri [34]. Kowalski [61]
showed how to efficiently construct oblivious protocols which work in optimal
time 0(klog).
A related leader election problem was studied by Jurdzinski, Kutylowski and
Zatopianski [56] for the channel without collision detection.
Aspects of dynamic selection on the multiple access channel by deterministic
protocols were considered by Kowalski [61]. That approach differed from the one
in this paper in that all the packets in a queue at a station could be combined
and sent as a single transmission at a round. Moreover, protocols were restricted
to be acknowledgementbased only, and the performance was measured in terms
of worstcase delay between injection and transmission of a packet.
3.5 Adversarial queuing
28
Adversarial queuing was introduced by Borodin et al. [11], as a framework to
study stability of routing protocols under worstcase traffic scenarios modeled
by adversaries. This approach interprets an execution of a protocol as a game
between the adversary and the protocol. For given directed network G adversary
in each round injects packets into a nodes. Each injected packet carries its path
to be traversed. The path is issued by adversary before injection of the packet.
Each packet having reached its destination is consumed and leaves the network.
Packet routing is limited by capacity of edges that is only one packet is allowed to
traverse an edge per one step. Thus all packets willing to traverse edge e in step
t have to be stored in queue at the end of edge e. In each round the scheduling
protocol decides which packet from the queue traverses edge. Adversary is also
limited by two parameters (A,w) where 0 < A < 1 is injection rate and w is the
window size. The interpretation of these two parameters is as follows. For each
edge e and any interval w consecutive rounds the adversary is allowed to inject
at most Xw packets which are scheduled to traverse edge e.
The goal is to develop scheduling protocol which prevents packet queues from
growing unbounded in infinite execution. We can see that injection rate A can
be at most 1 since one packet can traverse an edge per round. In [11] authors
consider following scheduling protocols:
FIFO (firstinfirstout). The precedence is given to a packet that was first
in the queue.
LIS (longestinsystem). The precedence is given to the packets that spent
the most time in the network.
NIS (newestinsystem). The precedence is given to the packet that spent
the least time in the system.
FTG (furthesttogo). The precedence is given to the packet that has the
most edges to be traverse.
NTG (nearesttogo) The precedence is given to the packet that has the
smallest number of edges to be traversed.
Authors show that all the scheduling protocols are stable for A < 1 on directed
acyclic networks however queues can be exponentially large in number of edges.
Next authors consider directed cycle of n nodes. Protocols FIFO and LIS are
29
shown to be unstable on cycle as opposed to FTG which is stable whit queues
of size 0(nw)
Andrews et al. [5] considered stability for rates p < 1. They defined a greedy
protocol to be universally stable when it was stable in any network for any
injection rate p < 1. Protocols furthesttogo (FTG), nearesttosource (NTS),
longestinsystem (LIS) and shortestinsystem (SIS) are proved to be universally
stable as opposed to firstinfirstout (FIFO), lastinfirstout (LIFO), nearestto
go (NTG) and farthestfromSource (FFS). Similarly, authors define a network to
be universally stable when it is stable for any greedy protocol and any injection
rate p < 1. They showed that the property of being universal could be decided
for a given network in polynomial time.
Aiello et al. [2] studied greedy adaptive protocols that handle packets knowing
only their destination nodes, while the adversary assigns paths to packets only
for the purpose to determine injection rate for every edge. They showed that
some protocols guarantee polynomial bounds on sizes of queues at nodes and
the times of deliveries for an adversary with injection rate p < 1.
Goel [52] gave a complete characterization of universally stable directed graphs.
Gamarnick [41] gave a complete characterization of bidirectional networks uni
versally stable under the condition that at most one packet crosses an edge at a
round.
Bender et al. [10] studied stability of randomized backoff on the multipleaccess
channel in the adversarial queuing model. Stability was defined to mean that the
throughput was lower than the arrival rate. They showed that exponential back
off was unstable as long as p > clglgn/lgn, for a sufficiently large constant c.
Regarding stability, they showed that loglog iterated backoff was stable when
p < c/ lg lg n lg n, and that exponential backoff was stable when p < c/ lg n, for
a sufficiently small constant c.
4. Asynchrony in multihop radio networks
The results described in this Chapter are a joint work with Bogdan Chlebus,
see [27].
4.1 Introduction
Broadcast is among the most natural and useful communication primitives. One
node of a network is designated as a source while the other nodes are assumed to
be reachable from the source along directed paths. The source holds a message
that needs to be disseminated among all the nodes in the network. Such a
dissemination is usually achieved by relaying the message from node to node.
We consider asynchronous broadcasting in packet radio networks. Radio net
works are represented by directed graphs. An asynchronous execution of a broad
cast protocol is a sequence of events, each representing transmissions occurring
simultaneously. The correctness of a protocol at hand is understood in the
context of a given adversary who schedules events with the goal to make the
broadcast not completed successfully.
A broadcast protocol for a given radio network specifies, for each node, how many
times the source message is to be retransmitted by the node. The total number
of transmissions over all the nodes is called the work of a broadcast protocol
and is used as the complexity measure. We study computational problems to be
solved by deterministic centralized algorithms for given input networks. One of
them is to find a broadcast protocol, given a network, another is to verify the
correctness of a given protocol.
Models of radio networks and synchrony. Radio networks studied in the
literature have been assumed to be synchronous. The synchrony in networks
denotes an environment in which time is partitioned into rounds. All nodes are
controlled by local node clocks ticking at the same rate. A stronger assumption,
usually also made, is that local clocks produce the same round numbers. Every
transmission by a node of a synchronous radio network occurs within one round
and occupies the whole round. A message sent at a round is delivered to the
recipients in the same round. A message delivered to a node may sometimes not
31
be heard, that is received successfully, in a radio network. The motivation for
this is that all messages are transmitted on radio waves of the same frequency
and so many arriving at the same round at a node interfere with one another.
The key properties of the synchronous mode of radio communication can be
summarized as follows:
(i) If a message is sent by a node at a round, then the message is delivered at
this round to all the outneighbors of the node.
(ii) A message is heard by a node when it is the only message that arrived at
the node at a round.
This paper proposes how to extend the synchronous mode of radio communica
tion to capture asynchrony. The assumption of synchrony seems to be essential
for radio networks, since the model is defined by the property that messages
arriving to a node at the same round collide and none of them can be received
successfully. Observe that the possibility of a collision of messages requires only
the ability to categorize transmissions as either occurring simultaneously or not.
In a synchronous scenario, both notions simultaneous and in the same round
mean the same. We abstract from round numbers and leave only the abstract
notion of occurring simultaneously. An execution of a protocol is defined to
consist of a sequence of abstract events. Any such event represents what oc
curs simultaneously. This approach is related to the methodology applied when
defining asynchrony in the theory of distributed computing, see the books on
this topic by Attiya and Welch [6] and Lynch [68].
We propose to restrict asynchrony by way of adversaries who control the timing
of arrivals of messages. We study three specific adversaries, called edge, crash
and node ones. The edge adversary is the most powerful one in that timings
of deliveries of messages my be independent for each traversed edge. The crash
adversary is defined to be the edge adversary augmented with the power to
crash some of the nodes before the start of an execution. The node adversary
is restricted by the property that all deliveries of copies of a message generated
by a single transmission of a node occur simultaneously.
Motivation. The standard approach to study radio networks is valid in environ
ments satisfying a number of tacit assumptions. One of them is that nodes given
in the networks specification are the only ones participating in communication
32
protocols. Another of the assumptions is that communication protocols can con
trol the behavior of the nodes to the extent that a protocol may be specified
as a schedule that determines for each node and each round whether a trans
mission by the node occurs or not at the round. Our motivation in introducing
asynchrony is to capture communication scenarios when these assumptions are
relaxed.
In one of the proposed models, asynchrony occurs because edges do not repre
sent transmission ranges, as typically is the case in the literature, but rather
disjoint paths in a larger network. The graph specified as the network under
consideration is actually a subnetwork of a larger communication structure, and
consists of only the nodes that are responsible for achieving the communication
goal. The communicating units omitted from the networks specification play
the role of auxiliary relay stations. These stations are busy performing other
tasks, but join from time to time to help route traffic by forwarding messages.
The following are natural assumptions about relay stations. Every message re
ceived by a relay station is eventually retransmitted. Transmissions by relay
stations can interfere with other transmissions only at the nodes of the explic
itly considered network. A relay station forwards each received message exactly
once. If one wants a relay station to repeat a transmission a certain number of
times, then the way to make it happen is to have the relay station receive the
message the same number of times. These properties provide a scenario in which
when a message is transmitted by a node of a radio network, then the message
will arrive at each neighbor of the node with some delay which is unpredictable
and which may depend on the neighbor. This model is formally defined by way
of the edge adversary, see Section 4.2.
In the second model, all the nodes are explicitly listed in the networks specifi
cation, but the nodes execute communication protocols concurrently with per
forming other tasks. When a message arrives at a node, it is stored temporarily,
and then sent at some future round. Nodes are not expected to follow a pro
tocol so that an execution for a node is a sequence of transmissions at rounds
known in advance. However, when a node does perform a transmission, then
this results in all its outneighbors receiving the message simultaneously. This
model is formally defined by way of the node adversary, see Section 4.2.
The third model incorporates failures. It is obtained by augmenting an adver
sary with the power to crash nodes. We consider only the case when the edge
adversary can crash nodes before the start of an execution of a protocol. This
33
model is formally defined by way of the crash adversary, see Section 4.2.
Summary of results. We propose how to study asynchrony in radio networks.
The main ingredients of our approach include (1) abstracting an execution as a
sequence of simultaneous transmissions called events, and (2) imposing restric
tions on events in the same execution to capture additional properties of the
model. Possible executions of a broadcast protocol are defined by way of adver
sarial models. We consider three specific adversaries, called edge, node and crash
ones. We show how to find, for a given input network, an asynchronous broad
cast protocol for the network. The workcomplexity of the obtained protocol,
measured as the total number of transmissions, may be exponential. We show
next that this is an inherent property of the model by proving exponential lower
bounds for each of the considered adversaries. The problem to verify if a given
protocol is correct, against either the edge or the crash adversary, is shown to be
polynomially solvable. The problem to decide if there is a protocol of at most a
given work complexity which is correct against the edge adversary is shown to
be NPcomplete. A notable difference between the edge and node adversaries is
that while the correctness against the edge adversary, for a given network and
protocol, is polynomially solvable, this problem for the node adversary is shown
to be complete in coNP.
Structure of this chapter. The chapter is organized as follows. Section 4.2
discusses the technical notions, in particular asynchronous executions. We dis
cuss ways to obtain a broadcast protocol, for a given radio network, in Sec
tion 4.3. Section 4.4 includes exponential lower bounds on the work of broadcast
protocols, with correctness understood with respect to any of the considered ad
versaries. In Section 4.5 we develop polynomialtime algorithms to verify if a
given broadcast protocol is correct, for the edge and crash adversaries, respec
tively. Section 4.6 contains a discussion of problems regarding asynchronous
radio broadcast that are complete in the complexity classes NP and coNP, re
spectively.
4.2 Technical Preliminaries
A radio network is modeled as a directed graph G = (V, E), where V ~V[G) is
a set of nodes, and E = E[G] is a set of directed edges. An edge (x, y) G E is
also denoted as x > y. When x y is an edge, then node x is its start point,
and node y is its end point, while x is an inneighbor of y and y an outneighbor
34
of x. The set of all inneighbors of y is denoted as in(?/), and the set of all out
neighbors of x is denoted as OUt(x). We assume that a network is represented
by lists of pointers to in and outneighbors of each node.
For a node x and each outgoing edge x y, there is a outgoing buffer outx(y) at
x associated with the edge. When the node x sends a message, then a number
of copies of the message are put into each such a buffer outx(z) at x, for an
outgoing edge x z. For a node y and an incoming edge x > y, there is an
incoming buffer in^rr) at y associated with the edge. When a message is removed
from the outgoing buffer outx(?/) and placed in the incoming buffer iny(a:), then
the message is said to be delivered from x to y.
Broadcasting occurs as a sequence of events, which are atomic components of
executions. An event consists of a number of deliveries and sendings of the source
message along edges of the underlying network. The deliveries in an event are
interpreted as occurring simultaneously. The number of deliveries at an event is
always positive, except for the initial event when the source performs the first
transmission. At most one message can traverse an edge from an outgoing to
the incoming buffer at an event. It is still needed to be specified how sending
is performed at events.
We distinguish a message being delivered from being heard, which means suc
cessfully received. A message delivered at node x at an event is heard at x if
it is the only message delivered to x at this event. If more than one messages
arrive at a node at an event, then none is received successfully by the node. It
is possible that some nodes hear the message at an event while others do not.
An event may trigger some nodes to send the source message just after it was
heard for the first time. This occurs as follows. When the source message is
heard at a node x for the first time, at a certain event, then x sends the message
in the same event. Subsequent events, in which x hears the message again, do
not result in sending by x. Sending is performed by placing a number of copies
of the source message in the outgoing buffers; the number of copies is as specified
by the executed protocol.
A broadcast protocol for graph G is determined by a function 3 : V[G] > N,
which assigns a nonnegative integer b(u) to each node v Â£ V[G], with the ad
ditional requirement that b(.s) > 0 for the source s. Such a function is called a
repeatbroadcast function and the value b(u) is called the repeatbroadcast value
35
of v. The protocol given by such a function determines how nodes sends mes
sages. When a node v sends a message, then this results in placing b(w) copies
of the message into the outgoing buffers of all its outgoing edges. We often refer
to the broadcast protocol determined by a repeatbroadcast function B by the
same name B.
Events are components of executions of protocols. An execution of protocol B
is defined to be a sequence 8 = (e0, e\,..., ef) of events, which satisfies the
following properties:
1. The first event eo of 8 consists of sending the source message by the
source s.
2. All the outgoing buffers are empty after the last event eg.
If a node v of repeatbroadcast value B(v) hears the source message at some
event, then deliveries of the message from v to any outneighbor have to occur
in B(v) events. If, on the other hand, v does not hear the source message at all
in an execution, then a delivery of the messages from v does not occur at any
event in this execution.
Observe that an execution if fair in the sense that any copy of the source mes
sage that is placed in an outgoing buffer is eventually delivered. An execution
terminates only when there is nothing to be delivered. An execution is said to
be successful when every node in the network hears the source message in the
course of the execution.
Further restrictions on executions are given in the framework of adversarial
models. The motivation is to capture additional properties of an asynchronous
mode of radio communciation.
The correctness of protocols is always understood for specific adversaries. Adver
saries are not necessary, since we could simply restrict the class of executions in
the same way as the adversary is defined. We consider three specific adversarial
models.
Edge adversary: It acts subject only to the general definition of an execution of
a given broadcast protocol.
Crash adversary: It is the edge adversary augmented with the power to fail nodes
by crashing.
36
Figure 4.1: A radio network with source S. The repeat
broadcast function equal to 1 at each node gives a protocol that is
correct against the node adversary but not against the edge one.
Crashes occur prior to the start of an execution of an algorithm. The faulty
nodes do not participate in executions, and may be considered removed
from the graph. This may make some nodes unreachable: such nodes are
also considered crashed.
Node adversary: It acts subject to the following additional constraint: if the
source message is received at a node from some node x, then the message
is received at all the outneighbors of x at the same event.
Given a broadcast protocol B and an adversary A, protocol B is correct against
A when every execution of B consistent with the power of A is successful. The
node adversary is more restricted than the edge one. A protocol that is cor
rect against the node adversary may not be correct against the edge one. As
an example, consider the graph on Figure 4.1 and a protocol with the repeat
broadcast function equal to 1 at each node. Observe that the only node with an
indegree larger than 1 is C, while each among the nodes A, B and D each will
hear the source message eventually. To see why this protocol is correct against
the node adversary, consider two cases. If the message from the nodes A and
D is delivered to C at the same event, then node B hears the message at the
same event, but a delivery from B to C cannot be blocked by a delivery from D.
Otherwise the first delivery of the message to C is heard by C. This protocol
is not correct against the edge adversary though, because it is possible that the
message is delivered to C from all A, B and D in the same event.

37
The work W(B) of a protocol B is defined to be equal to the sum of the repeat
broadcast values of all nodes of G, that is, W(B) = ^2veVb(v). Observe that
the length of an execution is at most J2vev b(w) deg(u) in the case of the edge
adversary, where deg(u) is the outdegree of v, since just one message may be
delivered in each event. This length is at most the work W(B) = ^Â£l/b(r) in
the case of the node adversary.
The definition of asynchrony we assume allows for any instance of a radio net
work with a distinguished source to have a correct broadcast protocol, as is
demonstrated in Section 4.3. This is not the case for gossiping. A problem of
gossiping has each node start with its rumor and the goal is for every node to
learn all the rumors. Conceptually, gossiping is equivalent to multiple concurrent
instances of broadcasting.
Proposition 1 There is a strongly connected radio network for which no repeat
broadcast function determines a gossiping protocol correct against the node ad
versary.
Proof: Consider a network of three nodes a, b and c, in which any ordered pair
of nodes in sets {a, b} and {b, c} is connected by a directed edge. In particular,
nodes a and c are connected to b but there is no edge between a and c. The only
way node a learns the rumor of node c, and vice versa, is to hear it relayed by
node b. It turns out that the node b may not learn all the rumors. To see this,
consider two cases for a protocol B. If B(a) = B(c), then each delivery from a
to b can be matched by a delivery from c to b, and so b may not learn any of
the remaining rumors. Otherwise, when B(a) ^ B(c), assume without loss of
generality that B(a) < B(c). Then any delivery from a to b can be matched by
a delivery from c to 6, so 6 may not learn the rumor of a.
4.3 Protocol by enforcing dominance
A node x is called a relay for node y if x > y is an edge and the distance from
the source to x is smaller than to y. Let S C V be a set of nodes. A node x 6 S
is said to dominate S if the inequality
b(z) > h(y>>
yes\{x}
holds, while the empty sum is assumed to be equal to zero. Each node different
from the source has at least one relay node, because all nodes are reachable. If
38
node x is an inneighbor of y and x dominates all inneighbors of y, then x is
said to guard the node y, which is also denoted x = L(y). A node x is guarded
if some inneighbor of x guards x.
Lemma 1 If, for each node y different from the source, there is a relay node that
guards y, then the protocol is correct with respect to any among the considered
adversaries.
Proof: We show, by induction on the distance from the source to y, that y
eventually obtains the message. If the distance is zero, then y = s and so y
holds the message. Suppose the distance is positive, let x be a relay node that
guards y. By the inductive assumption, x receives the message at some point. At
least one transmission from x cannot be matched and blocked by a transmission
from another neighbor of y. This holds because otherwise the total number of
messages at the remaining inneighbors of y would have to be at least as large
as b(:r).
Lemma 1 cannot be strengthened by assuming only that each node different
from the source is guarded by some neighbor. There are also protocols correct
against the edge adversary in which some nodes are not guarded by a neighbor.
Next we describe an algorithm DistanceDomination to find a protocol
correct against the edge adversary. The algorithm assigns values of repeat
broadcast function to nodes of a network G = (V, E) given as input.
Let us fix an enumeration of all nodes of G, such that if the distance
from the source s to Vk is smaller than the distance from the source to ve, then
I < k. In particular, we have that s = vn. Initialize the broadcast function
B(v) = 0, for each node v E V. It is next modified for each node, in the
increasing order of indices. Take an index i, such that 1 < i < n. Suppose all
1 < k < i have already been processed. Define
Cj = i +
xin(vj)
We set b(t>j) equal to the maximum value among Cj over all edges v, * Vj, if at
least one such an edge exists, and b(uj) = 0 otherwise.
A pseudocode of algorithm DinstanceDomination is given in Figure 4.2. The
summation uses a different range of indices than the one in (4.1), because b(uj)
39
Algorithm DistanceDomination ( G, s )
for each node v Â£ V[G] do b(u) := 0
find a tree of shortest paths from s
sort the nodes in reversed order on the distance from the source s
let (vi,... ,vn = s) be the resulting ordering
for i := 1 to n do
for each v3 Â£ ouT(uj) do
z :=0
if j
if b(nj) < 2 then b(uj) := z
Figure 4.2: Algorithm DinstanceDomination which finds a
repeatbroadcast function B for a given network G with source s.
plays the role of a local variable to store the largest value of z = C3 examined
so far.
Theorem 1 The algorithm DistanceDomination works in 0(n + m) time
and produces a protocol that is correct against the edge adversary. The work of
the obtained protocol is always smaller than 2n~1, where  V'j = n.
Proof: We show, by reversed induction on the distance from the source vn = s
to a node v3, that there is a relay node for v3 that guards v3. Let u* be a relay of
Vj of the largest index among such relay nodes. Then i > j and, by the definition
of the repeatbroadcast function, the value of b(ui) equal to
b(Ui) = 1 + ^ b(x)
was assigned last among values assigned to all the inneighbors of Vj. It follows
that the node Vi dominates all the inneighbors of v3. This shows that Lemma
1 is applicable, which yields correctness.
Next we show by induction on the indices of the nodes in the numbering (wj)i
that the inequality b(wj) < 2I_1 holds. For i = 1, we have b(ui) = 0 < 2,
because V\ is not a relay for any node. Consider i > 1 and let n, v3 be an
40
edge. At the time when b(vi) is computed, the values b(z) > 0 among in(wj)
occur only at x = Vk for k < i. Hence we may use the inductive assumption
b(vk) < 2k~1, and estimate
b(fj) = 1+ ^2 b(x)
<1 +
1
< i + Y22fc_1
1
= 1 + 2i~1 1
= 2i_1 .
This shows that b(uj) < 2I_1 for all ly. The work of the protocol Xu
can be upperbounded by the sum 5Zi
2n.
The workperformance of the protocol produced by the algorithm Distance
Domination is exponential, which cannot be improved in general, as we show
in Section 4.4. The obtained protocol is also a fortiori correct against the node
adversary.
One could observe that sorting the nodes by the distance to them from the source
in increasing order of indices, and then assigning 2l to a node ut as a value of a
repeatbroadcast function, results in a correct protocol. This is because any set
of nodes has a dominating element, hence Lemma 1 applies. If this is so simple,
why to develop the algorithm DistanceDomination? The answer is that for
some natural classes of graphs the work of a protocol obtained by this algorithm
is o(2n), for networks of n nodes.
Theorem 2 For networks with indegrees at most d, the work of the protocol
obtained by the algorithm DistanceDomination is 0(Cn), for some C such
that 1 < C < 2(1 2~d).
Proof: Follow the proof of Theorem 1. Numbers b(uj) satisfy the inequality
m
b(Um+l) < b^fc)
k=md
41
for i > d. Hence the inequality b(uj) < A{ holds, where the numbers Ai are
defined by the recurrence relation
Ak+d+i Ak+i + Ak+2 + + Ak+d
and suitable initial values. This is a definition of dround Fibonacci numbers.
Its characteristic equation is xd xd~l xd~2 ... x 1 = 0. The equation
has one positive simple root C in the interval [1,2], which satisfies the inequality
1 < C < 2(1 2~d), see [77],
Algorithm DistanceDomination is not applicable against the crash adver
sary. In this case, assigning 2l to a node V{ as a value of a repeatbroadcast
function results in a correct protocol. This approach is best possible as we show
in Section 4.4.2 by proving a matching lower bound.
4.4 Lower bounds
In this section we show that there are networks for which any broadcast protocol
requires exponential work.
4.4.1 Edge and node adversaries
We construct a family of networks Gn, each with n nodes, such that, for any
algorithm on Gn correct against the edge adversary, its work has to be at least
cn for some constant c > 1.
We first define a family of networks Fk, for each integer k > 0. The network Fk
has (*) + k + 1 nodes, partitioned into three layers. The top layer L0 consists
of only the source node. The middle layer Li consists of k nodes. The bottom
layer L2 includes the remaining (3) nodes. Directed edges connect the source
with each element of layer L\. There is a onetoone correspondence between
threeelement subsets of Lx and the nodes of the layer L2. For each 3element
subset X of Li, there is exactly one node v in the layer L2 such that X consists
of inneighbors of v.
Lemma 2 If a repeatbroadcast function for the nodes of Fk determines a broad
cast algorithm correct against the edge adversary, then, for each node v in the
bottom layer, there is a guard for v in the middle layer.
42
Proof: Let B be the repeatbroadcast function. Assume, by way of a contra
diction, that there is no guard for v. Let v2 and v3 be the inneighbors of v,
where b(ui) > b(u2) > b(u3). The adversary may use the following strategy to
block node v. First deliver the message to all inneighbors of v and then have
each transmission of v\ collide with a transmission by some other node. This
is achievable because V\ is not a guard for v. Namely, the first transmissions of
V\ can be blocked just by v2, and node v3 joins at the first round when there
are b(u3) > b(ui) b(w2) messages still to be sent by v\, and continues till the
end. This shows that the repeatbroadcast function does not define a correct
algorithm, which is a contradiction.
For a broadcast protocol for the network Fk, we can assume that it is consistent
with indexing of the nodes in the middle layer, in the sense that b(uj) < b(wj)
if and only if i < j, for 1 < i,j < k, because otherwise we could renumber the
nodes.
Lemma 3 Let B be a broadcast protocol for Fk correct against the edge adver
sary.
Then the following inequalities hold: B{vi) > 0 and B{vf) > /j_2, for k > i > 2,
where fa is the ith Fibonacci number.
Proof: Induction on k > 3. For k = 3, the middle layer consists of just three
nodes L\ = {vi,v2,v2} and the bottom layer consists of one node L2 = {},
while each node from L\ is an inneighbor of u. The least expensive among
correct broadcast protocols is defined as follows: B(s) = b(w3) = 1 and b(u1) =
b(u2) = 0. A base of induction holds, because /0 = 0 and f\ = 1.
Assume that the claim holds for Fk Consider a repeatbroadcast function B that
works for F^+i The subgraph induced by the nodes s, v\,..., Vk and the nodes
that correspond to all 3element subsets of {ui,...,Wfc} is isomorphic to Fk.
By the inductive assumption, we have that B(vi) > 0 and B(vi) > fi2, for
2
node in the bottom layer. By the numbering of the nodes, which makes the
repeatbroadcast function monotonous, the only possible candidate for a guard
43
is the node t>fc+1. We obtain
B(vk+1) > B{vk) + B(vk~ 1) + 1
> fk2 + fk3 + 1
> fk1 ,
which completes the proof.
Theorem 3 There is a sequence (Gn)n>\ of networks, such that Gn has n nodes
and any broadcast protocol for this network, that is correct against the edge
adversary, requires work, where f = (1 + Vf>)/2 is the golden ratio.
Proof: Take k = \nx/z\ and consider F*. The network Fk is of size 0(n). By
Lemma 3 and properties of Fibonacci numbers, the work of the algorithm is at
least
k k
Y b(u<) ^ Y = ~1
i1 i=2
Since fk is equal to 4>k/Vb rounded to a closest integer, the work of the algorithm
is at least
The node adversary is weaker than the edge one, in the sense that each algorithm
correct against the edge adversary is also correct against the node one.
Theorem 4 There is a sequence (Gn)n>i of networks, each ofn nodes and any
broadcast protocol for this network, that is correct against the node adversary,
requires work Q(c^), for a constant c > 1.
Proof: Modify the graphs used in a proof of Theorem 3 by inserting an
additional node in the middle of each edge. The power of the node adversary
on such graphs is equal to that of the edge one.
4.4.2 Crash adversary
We show that fl(2n) work is sometimes necessary to accrue for a protocol that is
correct against the crash adversary. This amount of work is then optimal, since
it is always achievable, as observed in Section 4.3.
Let B be a broadcast protocol and v be a node in the network distinct from the
source. The node v is said to be blockable for B if the crash adversary can crash
44
some nodes different from the source, possibly none, so that node v is reachable
from the source in the obtained network but does not receive the source message
in a certain execution of B. A protocol B is correct for the given network if there
is no node blockable for B in the network.
Lemma 4 Let B be a broadcast protocol for network G. If, for each node, any
set of its inneighbors contains a guard, then the protocol B is correct for G
against the crash adversary.
Proof: Let us assume that some node v of G is blockable for B. Let the adver
sary crash some nodes in such a way that v is reachable but v does not receive
the message in some execution. Take a shortest path (s,ui,... ,Uki,Uk = v)
from the source s to v. Let i < k be the smallest number such that Ui does
not receive the message in some execution of the protocol on this network. The
set of all nonfaulty inneighbors of u* that eventually receive the message in
this execution contains a guard. This implies that the message gets eventually
delivered to which is a contradiction.
We say that node v is vulnerable if a removal of an arbitrary subset S C IN(u)
of nodes of v and also of the node v does not disconnect the nodes in in(u) \ S
from the source s. Intuitively, a node v is vulnerable if, in a situation when any
proper subset of neighbors of v has been crashed, the remaining inneighbors
of v can receive the message before v receives it.
Lemma 5 Let a node v of G be vulnerable. If protocol B is correct for G, then
each subset of In(v) contains a guard.
Proof: Let us assume that protocol B is correct and the node v has no guard
in some subset S C In(u). Then the adversary has the following strategy to
block v. First, it fails the nodes in in(u) \ S. Next it delivers the message to all
nodes in S but not to v. This can be done because node v is vulnerable and the
protocol B is correct. Since there is no guard in S, all transmissions from the
nodes in S can collide. Hence v is blockable, which is a contradiction.
Lemma 6 Let V = {v0,..., un_i} and T : V N. If T has the property that
for each subset S C V there exists an element v Â£ S such that v dominates S,
then the inequality > 2l holds.
45
Proof: For n= 1, the set V contains just one node v0 and T{v0) has to be at
least 1 = 2. This provides a base of induction. Let us assume that the lemma is
true for n and consider n+1. Let us assume that F(v0) < F{vx) < ... < F{vn).
This implies F(vi) > 2l, for 0 < i < n 1. There has to be a dominating node
in {w0,..., vn}. Since F(vn) > F(vi) for 0 < i < n 1, we have that vn is the
only node that can dominate {v0,..., un}. The smallest possible value for F(vn)
is 1 + Â£r=oX 2i = 2n.
Theorem 5 There exists a network G of n nodes for which any protocol B
correct against the crash adversary has work I7(2n).
Proof: Consider a network H defined as follows. It consists of n nodes
partitioned into three layers. The top layer L0 consists of one source node s.
The middle layer Lx consists of n 2 nodes. The bottom layer L2 consists of
one node v. The node s is the inneighbor of each node from layer Lx and each
node from Lx is the in neighbor of the node v.
The node v is vulnerable, so by Lemma 5 there exists a guard in each subset
of L\. By Lemma 6, the smallest possible amount of work is achieved when the
nodes in Lx transmit 2, 21, ..., 2n~3 times, respectively. Hence the amount of
work is 17(2).
4.5 Verifying correctness of protocols
Given a network G with a source s and a repeatbroadcast function B, we con
sider the problem how to verify if the broadcast protocol determined by B is
correct against the given adversary adversary.
4.5.1 Correctness against edge adversary
For two nodes u and v, we say that node u depends on v if any path from the
source s to u traverses either v or a node w with b(w) = 0. If an edge u > v has
the property that u depends on v, then such an edge is said to be redundant.
An edge that is not redundant is called significant. If edge u > v is redundant,
then transmissions by u cannot block v from receiving the source message, since
node v receives the message before u. Redundant edges can be removed without
affecting the set of nodes that receive the source message, for any behavior of
the adversary.
46
1
3
3
Figure 4.3: A broadcast protocol in which each node has a guard
while the two rightmost nodes can be blocked. Numbers by the
nodes denote repeatbroadcast values.
We may start with removing all redundant edges. To identify redundant edges,
do the following. For each node v, first remove v and all nodes w with b(w) = 0,
and then identify all nodes than cannot be reached from the source by a directed
path. If node u is among them and u * v is an edge of G then this edge is
redundant. In the remaining part of this section we assume that all edges are
significant.
Lemma 7 If node v does not have a guard, then the adversary can block v from
receiving the message.
Proof: Let 2 be a neighbor of v with a maximum value b(^) among all
neighbors. The adversary has the message delivered to each neighbor of v but
not to v. This can be done because there are no redundant edges. Next the
adversary enforces each message sent by 2 to collide with at least one message
sent from some other neighbor of v. This is achievable because 2 is not a guard.
Lemma 7 implies that every node has to have a guard for the protocol to be
correct. This is a necessary but not a sufficient condition however, see Figure 4.3.
Lemma 8 If there is a guard of node v, and the guard receives the message,
then v also will receive the message.
Proof: At least one transmission by L(v) cannot be blocked by a neighbor
of v, because the node L(v) dominates them all.
47
procedure CheckNodeBlocked ( v )
if v = s then return false
BlockedNodes := {u} ; B(v) := 0
remove all redundant edges
repeat
NewNodesToBlock := 0
for each node u 6 BlockedNodes
if L(u) exists then
NewNodesToBlock := NewNodesToBlock U {L(u)}
B(L(u)) := 0
remove all redundant edges
BlockedNodes := BlockedNodes U NewNodesToBlock
until NewNodesToBlock = 0
if s G BlockedNodes then return true else return false
Figure 4.4: A procedure to verify if node v can be blocked by
the edge adversary.
Now we develop a routine to verify if a node v can be blocked from receiving a
message. A pseudocode for this routine is in Figure 4.4, where L(v) denotes a
function that returns a guard of node v. Notice that guards may change as the
repeatbroadcast function evolves.
The routine maintains a set BlockedNodes, which stands for the set of blocked
nodes, of nodes that cannot receive the message to block node v. Initialize
BlockedNodes = {u} and modify B so that B(v) = 0 since v will never broadcast
as a blocked node. Remove all redundant edges for this modified B. Lemma 8
implies that L(v) should not receive a message if v is to be blocked. Add the
node L(v) to the set BlockedNodes and modify the repeatbroadcast function B
so that B(L(v)) = 0. Now remove all redundant edges for such a modified B.
Next, for each node x in BlockedNodes, find its guard L(x) and add the guard to
the BlockedNodes while modifying B to be equal to zero on L(x). Keep iterating
this until at some point the set BlockedNodes stops to increase, which occurs
when there are no more guards to be blocked. If the source s is in BlockedNodes,
48
then the node v cannot be blocked, otherwise it can.
Lemma 9 The procedure CheckNodeBlocked is correct.
Proof: We define two invariants for the two nested loops: the untilinvariant
of the outer until loop, and the forinvariant of the inner for loop.
Repeatuntilinvariant:
The set BlockedNodes contains the nodes that cannot receive the
message to block v. The set NewNodesToBlock contains all nodes
that cannot receive a message to block all nodes in BlockedNodes \
NewNodesToBlock. All redundant edges, defined by a repeat
broadcast function which assigns zero to all nodes in BlockedNodes,
are removed.
We prove this invariant by induction on the number of iterations of the outer
loop. The base is by the following two cases.
Case 1: There is no guard for the node v.
Then BlockedNodes = {u} and NewNodesToBlock = 0 and B(v) = 0 and all
redundant edges are removed.
Case 2: There is a guard L(v) for node v.
Then BlockedNodes = {v,L(v)} and NewNodesToBlock = {L{v)} and B(v) =
B(L(v)) = 0 and all redundant edges are removed.
The untilinvariant holds in both of these cases. Let us assume that we enter
the until loop and the untilinvariant holds.
Forinvariant:
Before the zth iteration the following properties hold:
The set BlockedNodes = {i>i, w2, ..., nt_i, i/*,..., v^} contains nodes
that cannot receive the message to block v. The set NewNodesTo
Block contains the nodes that cannot receive a message to block the
nodes v\ through Vii in BlockedNodes. All redundant edges, defined
by a repeatbroadcast function in which the nodes in BlockedNodes U
NewNodesToBlock transmit zero times, are removed.
49
Algorithm VerifyEdgeCorrect (G, B)
Correct := false
for each node v G V[G] do
if CheckNodeBlocked(u) then Correct := true
if Correct then return given repeatbroadcast function is correct
else return given repeatbroadcast function is not correct
Figure 4.5: Algorithm VerifyEdgeCorrect to verify cor
rectness of repeatbroadcast function B, for the underlying network
G, against the edge adversary.
When the forloop is completed, then the forinvariant holds
and the set BlockedNodes equals BlockedNodes U NewNodesToBlock, so the
untilinvariant holds too.
When we exit the until loop, the set BlockedNodes contains all nodes that cannot
receive the message to block v, since the set NewNodesToBlock is empty. If
BlockedNodes contains the source s then the adversary has no strategy to block
v since the source always performs a transmission. If BlockedNodes does not
contain s, then the adversary can make the nodes in BlockedNodes never receive
a message, so v is blocked.
Theorem 6 Given a network G of n nodes, and a repeatbroadcast function
B, the algorithm, VerifyEdgeCorrect checks if the protocol B is correct
against the edge adversary in 0(n6) time.
Proof: Each node v is added to the set BlockedNodes at most once, since after
v has been put in BlockedNodes, its repeatbroadcast value is set to zero and v is
never a guard. The until loop can be executed up to n times. The inner for loop
takes BlockedNodes iterations. Each iteration consist of finding L(u), which
takes C?(in(u)) time per call, followed by removing the redundant edges in
Q(n3) time. The runtime of CheckNodeBlocked is 0{{ 1 + 21\n)n3) =
0(n5), which yields the total 0(n6) time.
50
Algorithm VerifyAgainstCrashes ( B )
remove all redundant edges
for each node v do
C := B
while L(v) exists for C do
C(L(v)) := 0
remove redundant edges for C
if In(u) is nonempty then
return v is blockable
return the protocol is correct
Figure 4.6: Algorithm VerifyAgainstCrashes to verify
correctness of B against the crash adversary.
4.5.2 Correctness against crash adversary
We want to be able to verify if a protocol B is correct for the given input
network G.
Lemma 10 If there exists a node v that is blockable by the crash adversary,
then there exist a node u that is blockable by crashing only some neighbors of u.
Proof: Suppose that node v is blockable. There exists a path (s, U\,..., it*., v)
of nonfaulty nodes and a node Uj such that all nodes in (uj,... ,Uk,v) do not
receive the message, while all nodes in (s,ui,... do receive it. Let S C
in(uj) be a set of nonfaulty neighbors of Uj. Let W C S be a subset of nonfaulty
inneighbors that are blocked. The nodes in W do not transmit hence there is
no guard in S\W to block Uj. The adversary has the following strategy to block
Uj by crashing only its inneighbors: the nodes in S \ W are not crashed and
the remaining inneighbors of Uj in iN(uj) \(S\ W) are crashed.
The adversary has the message delivered to all nodes in S\W. This can be done
since it was done to block v. Next all transmissions from the nodes in S \ W
happen to collide, which is achievable due to absence of a guard in S \ W. This
means that Uj is blocked as required.
51
Next we consider an algorithm to verify correctness of a protocol, by way of
checking if there exists a blockable node. For each node v check if there is a
subset S C in(w) such that S does not contain a guard. If for some node v such
a subset S is found, then this v is blockable, and the protocol is not correct,
otherwise B is correct. The algorithm is in Figure 4.6.
Theorem 7 The algorithm VERIFYAGAINSTCRASHES (Bj checks in 0(n5)
time if a protocol B for a network of n nodes is correct.
Proof: Correctness follows from Lemma 10. The outerfor loop takes n iter
ations. The innerwhile loop takes at most n iterations. Removing redundant
edges costs 0(n3). The total runtime is thus 0(n5).
4.6 Computationally hard problems
We present apparently unfeasible decision problems, regarding broadcasting in
asynchronous networks with timing of arrivals of messages controlled by adver
saries we study in this paper. The problems are hard in complexity classes that
are lowest levels of the polynomial hierarchy [42],
4.6.1 Hard for edge adversary
We will resort to NPcompleteness of the following problem, see [42].
Problem: Exact Cover by 3Sets (3XC)
Instance: A set S = {xi,... ,xzm} and a family of sets F = {Ci,..., C*,},
where each C* is a subset of S of size three.
Question: Can S be covered by all sets in some H C F in such a way
that each Xi Â£ S belongs to exactly one Cj H?
The first problem is about existence of a broadcast protocol with work bounded
locally.
Problem: EdgeAdversary 01 Radio Broadcast
Instance: A network G with a distinguished source.
Question: Is there a broadcast protocol for G correct against the edge
adversary and such that each node transmits at most once?
52
Theorem 8 The problem EdgeAdversary 01 Radio Broadcast is NP
complete.
Proof: The problem is in NP, because it is sufficient to guess a protocol of
a 01transmission pattern and apply the algorithm developed in Section 4.5 to
verify that it is correct.
Next we give a reduction of 3XC to the problem considered. Take an instance
of 3XC an build a network of three layers as follows.
The top layer L0 contains just the source s. The middle layer L\ contains
nodes Vi, for each C,. The bottom layer L2 contains nodes Yj, for each Xj. The
source s is an inneighbor of each node in L\. The node Vi of the middle layer is
an inneighbor of Yj if an only if Xj e Cj. There is a onetoone correspondence
between correct 01 broadcasting algorithms and covering subfamilies H C F.
Namely, we declare a set Ci to be in H if and only if the repeatbroadcast
function on V, equals 1. The property of S being covered by all sets in H is
translated into a property that each node in the bottom layer will have the
message delivered from at least one node in the middle layer. The property of
disjointness of the elements of H translates into a property that each node in
the bottom layer can have a message delivered from at most one neighbor in the
middle layer, which guarantees that the message will be heard.
The next problem is about existence of a broadcast protocol with work bounded
globally.
Problem: EdgeAdversary WorkBounded Radio Broadcast
Instance: A network G with a distinguished source, and a positive
integer W.
Question: Is there a broadcast protocol for G correct against the edge
adversary and such that its work is at most W?
Theorem 9 The problem EdgeAdversary WorkBounded Radio Broad
cast is NP complete.
Proof: The problem is in NP, because it is sufficient to guess a protocol of
a total work at most W and apply the algorithm developed in Section 4.5 to
confirm that it is correct. Next we give a reduction of 3XC to the problem
53
considered. Take an instance of 3XC an build a network of three layers as in
the proof of Theorem 8. Set the parameter W equal to m, which is one third
of the size of S. A broadcast protocol correct for this network and of work W
has to be determined by a repeatbroadcast function that assigns only values 0
and 1.
4.6.2 Hard for crash adversary
We will resort to NPcompleteness of the following problem, see [42].
Problem: Graph 3Colorability
Instance: A simple graph G.
Question: Can the nodes of G colored with three colors in such a way
that adjacent nodes have distinct colors?
We give a decision problem regarding broadcast protocols correct against the
crash adversary that is NPcomplete.
Problem: CrashAdversary 3Radio Broadcast
Instance: A radio network G.
Question: Is there a repeatbroadcast function for G that assigns at
most three transmissions to each node so that the resulting
broadcast protocol is correct against the crash adversary?
Theorem 10 The problem CrashAdversary 3Radio Broadcast is NP
complete.
Proof: We reduce the problem Graph 3Colorability to the problem
considered. Let graph F = (V, E) be an instance of Graph 3Colorability.
Construct a directed radio network H as follows. There are three layers of nodes.
The top layer L0 consists of just the source s. The middle layer Li consists of
all nodes V = R[F] of the graph F. The last layer L2 consists of the nodes
that correspond to the edges in F, each node in L2 representing one edge in
E = E[F], The source s is an inneighbor of each node in L\. Nodes u and v
in L\ are inneighbors of w in L2 only if the edge {u, u} corresponds to node w.
Observe that a node w in L2 has indegree equal to 2, while a node v in L\ has
54
its outdegree equal to its degree in F. Next we show the correctness of this
reduction.
Let us assume that broadcasting in radio network H can be achieved with at
most three transmissions per node by some protocol B. Each node v in L2 is
vulnerable. By Lemma 5, one among the two neighbors u and v of w is a guard.
Since there are only two of them, their repeatbroadcast values cannot be equal.
Observe that none of these repeatbroadcast values is equal to 0, since otherwise
the remaining neighbor of w could be crashed preventing node w from receiving
the broadcast value. Define a coloring C of F by setting C{v) = B(v), for a
node v in V[F) = L\. Since each node in L2 corresponds to an edge in F, the
protocol B yields a correct coloring of graph F by three colors.
Assume now that the nodes of graph F can be colored by 3 colors. Let C be such
a coloring of F. We have C(v) ^ C(u), for each edge {v, u}. Let the numbers 1,
2, and 3 be names of colors. Define a broadcast protocol B for H by setting
B(s) = 1, for the source node s, then setting B(v) = C(v), for each node v in
Li, and finally setting B(w) = 0, for each node w in L2. The repeatbroadcast
value for each node is at most 3. Correctness of the protocol can be argued as
follows. All the nodes in the middle layer L\ receive the source message after a
single transmission from the source. What remains to show is that any node w
will eventually receive the message. There are two inneighbors of w of distinct
repeatbroadcast values. If exactly one of them is crashed, then the surviving
node will relay the message to tu, If none of them is crashed, then Lemma 1
applies.
4.6.3 Hard for node adversary
The problem to verify the correctness of a broadcast protocol against the edge
adversary was shown to be solvable in polynomial time in Section 4.5.1. The
corresponding problem for the node adversary turns out to be complete in coNP,
which we show in this section.
The lowest levels of the polynomial hierarchy are defined as follows. Class P
consists of problems solvable in polynomial time. Class Ep = NP consists of
problems such that an instance has a certificate verifiable in polynomial time.
Class Ilf = coNP consists of languages whose complements are in Ep = NP.
Class Ep = NPnp consists of problems for which instances have certificates such
that the verification of their validity is a problem in IIP = coNP.
55
The reduction we give is from a problem about domino tilings. A domino tile is
a unit square with sides parallel to the coordinate axes and with colors assigned
to the sides. A tile is oriented, in the sense that its upper, right, lower, and left
sides are fixed. One color is distinguished, say, it is color white. A quadruple
(a, b, c, d) of colors, possibly with repetitions, is a domino type. A domino tile is
of domino type (a, b, c, d) when its upper, right, lower, and left sides are assigned
the colors a, b, c, and d, respectively.
Tiles are placed in unit square regions of the plane determined by a grid of lines
parallel to the coordinate axes and intersecting the axes at points of integer
coordinates. We will consider square n xn regions of the grid, for some positive
integer n. Let T be a set of domino types. A Ttiling of an n x n square in the
plane is an assignment of tiles of the types in T to the unit squares in the nxn
square subject to the following two constraints:
1. Any two adjacent tiles have matching colors on their common boundary.
2. The sides of tiles making the outer boundary are all colored white.
A domino tiling of nxn square grid can be interpreted as representing an
execution of a nondeterministic Turing machine, where columns correspond to n
contiguous memory cells and rows represent n consecutive configurations. Colors
encode the tape alphabet, the position of the head and the state. The input is
encoded by the bottom row of tiles, which could be assumed to be uniquely
determined by the the set of types and number n.
Problem: SquareinUnary Domino Tiling
Instance: A finite set T of domino tiles and an integer n in unary
notation.
Question: Is there a Ttiling of the nxn square?
The interpretation of tilings, in which rows represent configuration, explains why
SquareinUnary Domino Tiling is an NPcomplete problem, see [16]. We
show that the tiling problem can be reduced to the complement of the following
decision problem:
Problem: NodeAdversary Correctness Radio Broadcast
56
Instance: A network G with a distinguished source, and a repeat
broadcast function B for the nodes V[G] of G.
Question: Is the broadcast protocol B correct on G against the node
adversary?
Theorem 11 The problem NodeAdversary Correctness Radio Broad
cast is complete in coNP.
Proof: The complement of the problem belongs to NP because a strategy for
the adversary is a certificate that can be verified in polynomial time.
Given an instance (T,n) of SquareinUnary Domino Tiling, we want to
construct a radio network with the property that there is a Ttiling of the nxn
square if an only if the node adversary has a strategy to prevent a successful
broadcast in the network. The network we build has an nxn grid structure, in
that some boundary nodes can be visualized as located on boundaries between
unit grid cells of the nxn grid while other cell nodes can be visualized as located
inside the cells. Cell nodes are organized in pairs; one of the nodes is the left
and the other is called bottom node of the pair.
Each boundary node represents a color and each pair of cell nodes represents a
domino type. The following are restrictions on which colors and types are used
for specific boundaries and cells. Boundary nodes for inner boundaries represent
all possible colors of types in T. There is only one boundary node per each unit
cell outer boundary representing the white color. Pairs of cell nodes for inner
cells represent all possible domino types in T, while pairs of cell nodes for cells
on the boundary of the nxn square are exactly those that represent the types
with the white color on the outer sides of the cell. The assignment of a color
of the boundary is represented by exactly one node on the boundary receiving
the source message. Such a representation results from a selection made by the
adversary of the domino type for the cell.
The network is defined to include exactly the edges that make the following
deliveries happen. Each node in a pair of cell nodes matching the colors on
the lefthand size and bottom boundaries receives the message. A left node in
the pair receives the message from the lefthandside boundary node while the
bottom node of the pair receives the message from the bottom boundary node.
A boundary node on a vertical boundary with a cell to the right can transmit
to exactly those left cell nodes in this cell that have the corresponding color on
57
their left side. Similarly, a boundary node on a horizontal boundary with a cell
above can transmit to exactly those bottom cell nodes in this cell that have the
corresponding color on their bottom side.
In the first event of an execution, the transmission by the source delivers the mes
sage to all the boundary nodes on the outer boundary. In general, any following
transmission, in an execution that does not result in a successful broadcast, can
be interpreted as consistent with assigning domino types to some cells among
those with the property that unique boundary nodes on the lefthandside and
bottom boundaries of these cells hold messages, until an n x n tiling has been
determined. There is only one such a cell, at the bottomleft corner, immediately
after the first event in an execution.
There are two special nodes, called the blocker and the relay, and a number of
additional special nodes called bad. The nodes have special roles to play, which
is achieved by way adding to the network specific edges as stipulated next. The
relay node can transmit directly to any other node in the network. The blocker
node can transmit directly to the relay node. If the relay node receives the
message, then it will perform sufficiently many transmissions to have one of
them performed as the only node in the event. If the blocker node receives
the message before the relay node while no bad node has received the message
yet, then the blocker has a sufficiently large repeatbroadcast value to perform
sufficiently many transmissions to block the relay node from ever receiving the
message. Each bad node can transmit directly to the relay node. When at least
one bad node receives the message, then also the relay node will receive the
message eventually. The exact values of the repeatbroadcast function assigned
to the nodes are explained later.
The underlying idea is that the only way for the adversary to inform the blocker
node without informing the relay node or any of the bad nodes is by way of
simulating a domino tiling. The construction guarantees this property by the
topology of the network. One component of the design provides that exactly one
node on any boundary has to receive the message, in order to represent selecting
a color for this boundary. Another component is that every left cell node in the
top right corner cell can transmit to the blocker node, and no other node can
do this. When such a node receives the message, but no bad node has received
the message yet, then a tiling has been completed.
58
Next we describe the machinery to simulate a tile selection for a cell. Consider
a specific cell, and assume that both exactly one boundary node, say, x on the
lefthand side and exactly one boundary node, say, y on the bottom side hold
the message. We want these two nodes to transmit in the same event. Add a
bad node for the cell with edges from any boundary node, like x and y, allowing
these boundary nodes to transit directly to the bad node. If a pair of boundary
nodes transmit together in the same event, then there is a collision at the bad
node. After the nodes x and y transmitted, then exactly the nodes in pairs of
cell nodes representing a tile with the color of x on the left and the color of y
at the bottom both receive the message. There may be many such pairs for the
cell. Some pairs of cell nodes may have only one node holding the message while
the other does not.
Consider a pair of cell nodes, say consisting of a and b, where a is a left node
and b is a bottom one. Let node a can transmit directly to every boundary
node on the top boundary, unless the outer boundary colored white is at the
top. Similarly, let node b can transmit to every node on the righthand side
of the cell, unless the outer boundary colored white is on the right. To make
only singleton nodes on these two boundaries receive the message, node a can
transmit to every node on the right boundary representing a color different from
the color of the type represented by the pair, while similarly node b can transmit
to every node on the top boundary representing a color different from the color
of the type represented by the pair; subject to the same restriction on white
outer boundaries. We want the two nodes in only one such a pair transmit
simultaneously. To enforce a simultaneous transmission of the two nodes in the
same pair, add a special bad node for the pair, similarly as for x and y. Consider
two such pairs. We want to have a mechanism that allows only one of them to
transmit. To exclude separate transmissions, add a bad node for the pair of
left components of the pair. Observe that a simultaneous transmission by two
different pairs would result in no node on the top and righthand side boundaries
receiving the message, whichever do not belong to the outer boundary, so it is
excluded. This property works except for the top right cell, which is an exception
that is handled differently as explained later.
Next consider the top right cell. When a tiling has been successfully simulated,
there is exactly one pair of cell nodes representing the tile with the lefthand
side and bottom side colors as given by the boundary nodes holding messages,
and with the righthand and top sides colored white. Add edges that allow each
59
cell node in this cell to transmit to the relay node, while only one node, say left,
of a pair can transmit to the blocker node. This guarantees that the two nodes
in a pair need to receive the message, because two of them need to transmit
simultaneously to inform the blocker while not informing the relay.
Now we describe the values assigned by the repeat broadcast function to the
nodes of the network. The function has properties to provide the required prop
erties of special nodes, like relay, blocker and bad ones. Each among the source,
boundary and cell nodes is assigned 1 as the value of the repeatbroadcast func
tion. Let r be the number of such nodes. The blocker nodes obtains r as its
rep eatbroadcast value. Name all the bad nodes as bo, blf ..., bk Assign repeat
broadcast value (r + l)2l to node bi, for 0 < i < k. This assignment has the
property that if any subset X of bad nodes receives the message and j is the
largest index of a node bj in this set, then there is an event in which bj is the only
node in X transmitting, because Yho
Finally, the relay node receives the rep eatbroadcast value larger by 1 than the
sum of the repeatbroadcast values of all the remaining nodes.
The specification of the network and of the repeatbroadcast function has the
property that some among the nodes do not receive the message in an execution
if and only if the blocker node receives the message, which occurs if an only if
anuxn tiling is represented by this execution. This shows the correctness of
the reduction.
The problem EdgeAdversary WorkBounded Radio Broadcast was
shown in Section 4.6.1 to be complete in NP. The corresponding problem for the
node adversary is as follows.
Problem: NodeAdversary WorkBounded Radio Broadcast
Instance: A network G with a distinguished source, and a positive
integer W.
Question: Is there a broadcast protocol for G correct against the node
adversary and such that its work is at most W?
The problem NodeAdversary WorkBounded Radio Broadcast is in
Â£2 To see this, observe that a broadcast protocol is a certificate whose correct
ness is an instance of a problem in coNP, since the correctness means that for
60
every execution the broadcast is completed successfully. We conjecture that the
problem is complete in Â£Â£.
61
5. Averagetime complexity of manytoall communication
The results given in this Chapter are a joint work with Bogdan Chlebus and
Dariusz Kowalski, see [26].
5.1 Introduction
We consider average cost of distributed communication protocols in adhoc radio
networks. Mobile radio networks may change their topology over time. This
justifies developing distributed communication protocols that are optimal in
average case.
Networks are adhoc, in that protocols do not rely on the knowledge of the
topology; the only information about the network that may be a part of code
of a protocol is the size n, which is the number of nodes. Initially, some k
among the nodes are simultaneously activated with input data; these data are
called rumors. The communication task is to make all the nodes in the network
learn all the input rumors. This communication task can be called manytoall
communication (M2A). The special case in which k = n is called gossiping.
Nodes exchange packets carrying rumors. A node sends at most one packet
per round. How the capacity of a packet is related to the size of a rumor may
affect the mode of operation of protocols. We consider two cases located on the
opposite sides of the spectrum of possible scenarios. In the model of combined
messages, a packet can carry all the rumors. In such a setting, it is natural to
have a node send all the rumors learned so far in any transmitted packet. In the
model of separate messages, a packet can carry only one rumor. With such a
restriction, a protocol needs to rely on a mechanism to prioritize rumors so that
a node sends a rumor of the highest current priority at a round.
The protocols we study are deterministic. The time of an execution of a protocol
is defined to be the first round when the communication goal has been achieved.
Such a completion of the communication task is not required to be known by
the nodes. The complexity measure we investigate is the average time as a
function of the size n of the network. To find the average time for size n, first
compute conceptually the durations of executions of the protocol on all strongly
I
I
62
connected networks of size n, and next take the average of the times accrued for
these networks.
Our results. We give upper and lower bounds on the averagecase complexity
of gossiping and manytoall communication. Protocols are distributed and de
signed for both the models of combined and separate messages. Let n denote
the size of a network and k the number of nodes activated with rumors. The
summary of the contributions is as follows.
I. Gossiping with combined messages can be performed in the average time
0(n/ \ogn), which is shown to be optimal.
II. We show that M2A communication can be performed in the average time
0(mm{k\og(n/k), n/ logn}) with combined messages and that fi(A:/lograt
logn) is a lower bound.
III. Gossiping with separate messages can be performed in the average time
0(nlogn), which is shown to be optimal.
IV. M2A communication can be achieved in the average time 0(k log(n/k) log n)
with separate messages. We show a lower bound fl(A;logn).
The optimal complexity of gossiping is found for both models of combined and
separate messages. The upper and lower bounds for the general manytoall
problem that we give are close to each other within polylogarithmic factors.
Previous work. Broadcasting in radio networks with topology modeled by
random graphs was considered by Elsasser and G^sieniec [38], who showed that
Oilogri) expected time was optimum for distributed protocols. This result can
be interpreted as giving the optimum averagetime complexity of broadcasting.
The authors of this paper do not know of any other results related to the average
time complexity of communication in radio networks.
A manytomany communication problem in radio networks, similar to what we
consider, was studied by G^sieniec, Kranakis, Pelc and Xin [43]. The problem
is defined as follows: There is a set S of k nodes initialized with rumors and
every one among these nodes needs to get to know all the rumors. Networks are
undirected, each node knows the topology of the network but does not know the
set S, the maximum distance d among any pair of nodes in S is an additional
63
parameter. A protocol solving this problem of time complexity 0{d\og? n +
klog3n) was given in [43].
Structure of this chapter. The rest of the chapter is structured as follows.
The technical assumptions are given in Section 5.2. Gossiping with combined
messages is discussed in Section 5.3. The general M2A communication problem
for the model of combined messages is presented in Section 5.4. Section 5.5
covers gossiping with separate messages, while Section 5.6 presents the results
about M2A communication with separate messages.
5.2 Technical preliminaries
We assume classical model of adhoc radio network. Radio network is repre
sented by directed graph G = (V, E). Each node has assigned unique id from
range [n]. The only information about network topology that can be used by
protocol is size of the network n Nodes are synchronized by global clock num
ber. Transmission from a node reaches all its out neighbors in the same round.
Node v can successfully receive transmission from its inneighbor u provided u
is the only inneighbor of v transmitting in the round. If there are at least two
inneighbors of v transmitting in the same round then collision occurs at v and
node v cannot successfully receive any messages.
Communication problems. Initially some nodes hold their input data called
rumors. When node i is initialized with a rumor, then this rumor is denoted by
tv The goal of communication protocols is to disseminate such input rumors.
In the problem of broadcasting, only one source node is assumed to hold an input
rumor and the goal is to make every node know the source rumor. Broadcasting
may be called a onetoall communication problem. In the problem of gossiping,
each node v is a source for its private input rumor rv, and the goal is to have all
the nodes learn all the rumors. Gossiping may be called alltoall communication
problem.
A generalization of gossiping called manytoall problem, or simply M2A, is
about a scenario in which only some of the nodes have input rumors. Such
nodes are called spontaneously activated or simply activated. The goal is to have
all the nodes in the network get to know all the rumors of the activated nodes.
All nodes in the network participate in forwarding messages in the course of an
execution of an M2A protocol.
64
To have a communication problem in radio networks meaningful, we need to
assume that the topology of the underlying graph makes the communication
task at hand possible to perform. In the case of broadcasting, one assumes that
all the nodes are reachable from the source node. In the case of gossiping and
M2 A, the graph is assumed to be strongly connected.
Communication protocols. Correctness of a protocol means that the commu
nication goal is eventually achieved on any strongly connected network. Nodes
running a protocol are not required to reach eventually a state representing the
completion of a task. This is assumed to decouple termination from complexity
considerations. The time complexity of a protocol at hand, for a given strongly
connected network, is defined to be the first round when the communication
goal has been achieved.
The size of messages affects the design of communication protocols. There are
two natural scenarios. One, of combined messages, assumes that all the input
rumors can be placed in a single packet and transmitted between two nodes in
one round. An alternative approach, of separate messages, stipulates that each
individual rumor has to be transmitted by a separate message.
Average complexity. The average time complexity of a deterministic com
munication protocol A on directed networks of n nodes is defined to be the
expected time complexity of A on a random directed radio network of n nodes.
Such a network has the property that for any ordered pair (i,j) of nodes, for
0 < i,j < n, edge z > y is in the network with probability 1/2, these events
independent over all the pairs.
We consider the average time complexity of gossiping and m2a communication on
stronglyconnected networks. The corresponding probabilistic space consists of
all strongly connected networks on n nodes as elementary events, each occurring
with the same probability. A random directed network is strongly connected
with the probability exponentially close to 1. This fact allows to obtain the
expected time estimates while working with arbitrary random directed networks.
These estimates are the same when they are conditional on the networks being
strongly connected, provided the time estimates are polynomial. An explicit
termination in polynomial time could be obtained for all protocols we develop,
since there are polynomialtime worstcase time estimates for these protocols,
valid for strongly connected networks.
65
We want m2a protocols not to have their performance biased towards specific
sets of activated nodes. Therefore we work with the average complexity of
m2a protocols defined in an adversarial manner as follows. Suppose there is an
adversary who is given a protocol V for n nodes together with a number k < n.
The adversary chooses a set K of k specific names of nodes to be activated; the
goal of the adversary is to show a scenario maximizing the complexity of the
protocol. The average complexity of protocol V, for nnode networks, is defined
to be the average complexity of protocol V measured when exactly the nodes in
K are activated with rumors.
An alternative equivalent definition of the average complexity of m2a protocols is
as follows. There are given numbers k < n and an m2a protocol V for networks
of n nodes. For any set K of k nodes among n, consider the average complexity
of V on all networks with nodes in fC activated spontaneously. Next take the
maximum average complexity over all such sets K. as the average complexity of
V for size n.
Probabilistic inequalities. We use the following Chernoff bounds, see [70]
for a detailed exposition with proofs. For a sequence of Poisson trials, let X be
the number of successes and /j, the expected value. The probability of deviation
below /j, can be estimated by the inequality
Pr[X < (1 J)//] < exp{<5V/2} , (5.1)
for any 0 < S < 1
the inequality
The probability of deviation above /.i can be estimated by
Pr[AT > (1 + %] <
(Â£
Ml+<5)
(5.2)
for any 5 > 0.
5.3 Gossiping with combined messages
We show that gossiping can be performed with the cn/lgn average time, for
any fixed c > 1, and that the average time always has to be at least cnj lgn, for
any fixed c < 1/2. (The logarithm of x to the base 2 is denoted by lgx.)
Gossiping protocol for combined messages Let Â£n = [n/61gn], where
6 = (1 + 1). Observe that the inequalities 1 > b > \ jc hold. Define group Qk,
for 0 < k < in, to consist of these nodes i, for 0 < i < n, that have the property
66
that the congruence i = k (mod in) holds. The size of a group is about feign.
The sizes of two groups differ by at most 1.
We consider an oblivious protocol GossipCombinedMessages, which is
given in Figure 5.1. A transmission by a node contains all the rumors that the
node has already learnt in the execution. The protocol consists of two phases.
The first phase uses groups as transmissions. Every node participates in exactly
one transmission during the first phase. The second phase consists of calling
RoundRobin. Protocol RoundRobin is structured as an unbounded loop,
but n2 rounds are sufficient to complete gossiping.
Theorem 12 For any c > 1, the average number of rounds to complete gos
siping by protocol GossipCombinedMessages on a network of n nodes is
smaller than cn/\gn, for a sufficiently large n.
Proof: Take a node y and group Q\~ Let x be in Gk The node y can hear x
at the kth round of the first phase when the following two events hold:
(i) x is an inneighbor of y\ and (ii) no other node in Gk is an inneighbor of y.
It follows that the probability of the event that y hears x Gk during the fcth
round of the first phase of the protocol is
2~\Gkl = 2blgn = n~b .
Let x and v be two nodes. Node y is called a relay for the pair (x, v) when the
following holds:
(i) y is an inneighbor of v; and (ii) y heard x in the first phase.
Observe that
Pr [y is a relay for (x, u)] = ^ ,
because the events y heard x in the first phase and y is an inneighbor of v"
are independent.
Consider the first t nodes, that is, the nodes i with 0 < i < t. These nodes are
scheduled to perform a transmission among the first t rounds of the protocol
RoundRobin in the second phase. Node i may make node v learn the rumor
rx of x if i is a relay for the pair (x,v). For all such nodes i making the first t
transmission during RoundRobin and different from x and v, the events z is
a relay for the pair (x, v) are independent.
67
for k := 0 to Â£n do
if v is in Qk then transmit
call RoundRobin
Figure 5.1: Protocol GossipCombinedMessages; code for node v.
If v has not learnt rx in the first t rounds of the second phase, then no i such that
0 < i < t is a relay for the pair (x, v). The latter event holds with probability
(1 by the independence of the events of being a relay node. It follows
that v does not learn rx in the first t rounds of RoundRobin with probability
of at most (1 )h
We use the inequality
(1;)
which holds for real s > 1. It yields the following estimate:
Let d = min{26,1}. Take t = na where b < a < d. Now the righthand side of
(5.4) becomes
exp(n_6/2) exp(na_d/8) = exp(na~6/2)(l + o(l)) . (5.5)
Consider the event that for any pair of nodes (x, v) there is a relay node during
the first t rounds of the second phase. The event does not hold with probability
of at most
n2 exp(^~)(l + o(l))
by the estimate (5.5). If this event holds, then gossiping is completed by round
2^ + na, which is smaller than ^ for sufficiently large n. Otherwise the time
68
of gossiping can be estimated by + n2. Combine all the estimates to obtain
that the expected value of the time of protocol A to complete gossiping is at
most
(b^n + n) ^ ~ ^ exP(~na_6/2)(l + o(l)) +
+ n2)"2exP("a"V2)(l + o(l))
for all sufficiently large n.
Lower bound for gossiping with combined messages. We show that any
gossiping protocol for the model of combined messages has the f}(n/ logn) aver
age time complexity. This implies that protocol GossipCombinedMessages
is asymptotically optimal.
Theorem 13 For any c < 1/2 and a gossiping protocol A for the model of
combined messages, the average number of rounds to complete gossiping by A
on a network of n nodes is larger than cn/\gn, for a sufficiently large n.
Proof: We define an auxiliary random variable X on the domain of all the
directed graphs of n nodes. For any such a graph G, run A on G and let s be
the first round when the gossiping has been completed: define X(G) = s.
We estimate the probability of the event X > s, for integer s > 0. Define the
event H(u, s) to hold, for node v and round s, when no node has heard from
node v by round s. Observe that
Pr [X > s] > Pr [H(u, s)] . (5.6)
We want to estimate the probability that H(u, s) holds.
We start with choosing v. Let an execution of A be given as a sequence
(T0, T\,T2,...) of transmissions. If some node v does not belong to any of the
first s transmissions, then such v yields the best possible estimate Pr [H(u, s)} =
1, which also implies that EX > s. Assume that every node belongs to at least
one among the first s transmissions of protocol A. Next we restrict our atten
tion only to these transmissions. We claim that there is a node, say, v with the
property that every transmission Tj that v belongs to, for i < s, is of size at least
T > n/s. This is because otherwise, even if every node belonged to only one
transmission, the total number of nodes in the initial segment of s transmissions
69
of A were smaller than n, which would contradict the assumption that these
transmissions include all the nodes.
A node x hears from v at round i < s, provided v e Tt, when the following two
events hold:
(i) v is an inneighbor of x in TJ, and (ii) no other node y A x in T{ is an
inneighbor of x.
This implies that the estimate
Pr [x hears from v at round %  v E T)] < 2~n^s
holds. Node v could belong to a number of transmissions T) for i < s, so we use
the estimate
Pr [x hears from v in the first s rounds] < s2 n^s .
Node x was arbitrary, and we need to be concerned with all the nodes. We use
the estimate
Pr [some node hears from v in the first s rounds ] < ns2 n^s .
The event H(u, s), that no node hears v during the first s transmissions, holds
with probability of at most
Pr [H(w, s)] > 1 ns2n/s . (5.7)
To estimate the expected value EX of X, we use the formula
OO
EX = Y, Pr [X > k] ,
k=0
which holds true for any random variable X with nonnegative integer values.
Combining this with the estimates (5.6) and (5.7), we obtain the inequality
t
EX > (1 nk 2~n/k) (58)
*=i
for any integer t > 0.
Let ko be the largest value of k for which the expression 1nk 2~n!k is positive.
We take the upper bound t on the range of summation in (5.8) to be close to k0.
70
Next we estimate the magnitude of k0 as a function of n. Observe that k0 is the
largest k for which the inequality
nk < 2n/k (5.9)
holds. Take the binary logarithm lg of both sides of (5.9) to obtain the equivalent
inequality lgn + lg k < f, which implies k0 = ^(1 + o(l)). We use the value
t = n/(21gn) in the estimate (5.8) to obtain
n/(21gn)
E X> ^ (lnk2~n/k)
fc=i
n
2 lgn
n/(21gn)
 E
fc=i
k 2~n/k
(5.10)
The function f(k) = k2~nfk is increasing as k > oo. The value f(t) =
/(n/(21gn)) is the largest term in the sum on the righthand side of (5.10).
Observe that
m
u 2~2Xzn
2 lgn
n
2 lgn
n
2
1
2nlgn
and hence the estimate
n/(21gn)
y k2^k<
zrl 21Â§n
l l
2nlgn 4 lg2 n
holds. Therefore (5.10) can be bounded below as follows:
n n n , 1
EX >
2 lg n 4 lg2 n 2 lg n
which completes the proof of Theorem 13.
^ 21gn^
5.4 Communication m2a with combined messages
Suppose k nodes among n in the network are activated with rumors. We give
a protocol with the 0(min{klog(n/k), nj logn}) average time complexity. We
assume that A; is a power of 2.
Two schedules V\ and V2 of transmissions are said to be interleaved, when the
consecutive actions as specified by V\ are performed in evennumbered rounds,
71
for i :\gk downto 0 do
call SelectorSubroutine(2*)
continue RoundRobin for lOlgn rounds
Figure 5.2: Procedure M2ACombined(A;).
while V2 determines the actions for the oddnumbered rounds. Infinite schedules
of transmissions are called protocols, while finite schedules are called procedures
in this paper. When a procedure V\ is interleaved with a protocol P2, then
eventually P\ ends. At this point we make the protocol V2 take over completely,
such that its actions are performed in all the following rounds; this is explicitely
marked in the pseudocode of our protocols by the instruction continue V2.
Another mode of using a protocol V specifies that the schedule of V is repeatedly
executed for an interval of x rounds, then it is frozen. This is indicated in the
pseudocode by the instruction continue V for x rounds.
We use families of sets called (n, j)selectors in [31]. They are defined as follows.
A set Y selects element v from a set X when X D Y = {u}. A family T of
subsets of [n] = [0, n 1] is an (n, j)selector when, for any set X C [n] of size
at most j, at least X/2 elements in X can be selected by the sets in T. The
size of T is called its length. We refer to any used selector T as a sequence
T = (Fi, F2,...) in an arbitrary fixed order.
Selectors are used to determine schedules of transmissions. Given a positive
integer number i and an (n, ^selector T, we define SelectorSubroutine(Â£)
as follows. The node v transmits in round i if v 6 Fp, rounds are counted from
the call of this subroutine. We use (n, 2l)selectors of length 0(2Mog(n/21)),
which were proved to exist in [36].
An m2a procedure, representing the case when k may be a part of code, is given
in Figure 5.2. Protocol M2ACombinedMessages is given in Figure 5.3.
Next we analyze the average complexity of the protocol.
A node v is said to be a unique transmitter at a round, when v is the only
node transmitting at that round. We say that broadcast of rv was success
72
for j := 0 to lgn do
call M2ACombined(2j) interleaved with GossipCombined
Messages
continue GossipCombinedMessages
Figure 5.3: Protocol M2ACombinedMessages.
ful/completed, or that node v broadcast successfully, when every node has re
ceived rv.
Lemma 11 Suppose that node v transmits its rumor rv as the unique trans
mitter, and after this RoundRobin is executed. Then the broadcast of rv is
completed in at most 10lgn following rounds of RoundRobin with probability
of at least 1 1/n3.
Proof: Consider any consecutive 10lgn rounds of RoundRobin, where the
numeration starts from the first of these rounds. Assume that node v is the
unique transmitter at the first round.
Let v = V\, V2, ..., fioign be the sequence of transmitting nodes. Let w be a
node. If there is a relay or an edge from v and w, then the node w receives rv.
We consider the event that there is a relay node u* for node w such that there is
a directed path v > w in the graph. The probability that there is neither
a relay among nodes u2, ..., Pioign for nodes v and w nor a direct connection
from v to w is at most
It follows that the probability that there is a node with neither a relay from v
Theorem 14 Protocol M2ACombinedMessages has
0(min{A;log(n/fc),n/logn}) average time on networks of n nodes with any k
activated nodes.
nor a direct connection to v is at most n 1/n4 = 1/n3.
73
Proof: We show first that the protocol completes the m2a task by the end
of the loop for j = [lgfc] with probability of at least 1 4k/n3. The protocol
calls the procedure M2ACombined(2j), which in turn involves Selector
Subroutine^). Since there are k < 2J activated nodes, during Selector
Subroutine(2?) at most 271 activated nodes did not transmit as unique trans
mitters. Being a unique transmitter results in a successful broadcast during the
next RoundRobin part, with probability of at least 1 1/n3 by Lemma 11.
During SelectorSubroutine(271), at most 2?2 activated nodes did not
transmit as unique transmitters, since there are at most 2^~l participating nodes
with probability of at least 1 2J/n3. These nodes that transmitted as unique
transmitters have a successful broadcast during the next rounds of Round
Robin with probability of at least 1 2i/n3 2J_1/n3.
In general, in an execution of SelectorSubroutine(21) within
M2ACombined(2j), there are at most 2l activated nodes for which broadcast
was not successful during the previous iterations with probability of at least 1
j2a/n3. Conditional on this event, during SelectorSubroutine(2*)
at most 2l_1 of the activated nodes did not transmit as unique transmitters. It
follows that after the zth iteration of the loop, at most 2l~l rumors have not
been broadcast successfully with probability of at least 1 2a/n3.
M2ACombined(2j) completes m2a for k activated nodes in time
j
^ 0(2* log(n/2l) + logn) < 0(k\og{n/k))
i=o
with probability of at least 1 ^=0 2/h3 > 1 4k/n3. Including also the
previous executions of M2ACoMBINED(27,) for / < j, yields the time estimate
^2 0(2j> log(r^/2?,)) = 0(k\og(n/k)) .
j'
Since 0{n2) is the worstcase time bound, the average time of M2ACOMBINED
Messages is 0(klog(n/k)) + 0(n2) 4k/n3 = 0(k\og(n/k)).
Theorem 15 The average cost of an m2a protocol in the model of combined
messages is tt(k/logn + logn) on networks of n nodes with some k of them
activated.
74
Proof: Let A be an m2a protocol. Fix a set K of activated nodes, where
\K\ = k. Let (T0,7\,...) be the sequence in which T, denotes the set of nodes
transmitting at round i in the execution of A. We consider two kinds of rounds
i:
Case 1: Rounds i in which Tj includes at most 41gn nodes in K that transmit
for the first time.
Even k/(4lgn) such rounds are not sufficient to exhaust all the elements in K.
Case 2: Rounds i in which there are more than 4 lg n nodes from K transmitting
for the first time.
We show that there is no successful transmission between any pair of nodes up
to round s = k/(4lgn) with a large probability in any round. Take node v. Let
a = Tj > 41gn. The probability that v receives a rumor for a node in Tj at
round i is f ()a_1 > for sufficiently large n. It follows that the probability of
existence of a node that receives a rumor at round i is smaller than 1/n2. The
probability that some node receives a rumor by round s is smaller than s/n2.
The expected value of the number of rounds by completion of the communication
task is at least s (1 for n > 2.
The complexity of protocol M2ACombinedMessages given in Theorem 14
is close to the lower bound given in Theorem 15 by factor C9(lognlog(n/Â£;)).
5.5 Gossiping with separate messages
Now we consider gossiping in a scenario when input rumors are so large that
it takes a separate packet to carry one rumor. We show that gossiping can be
performed with the 0(n\ogn) average time, and that the average time has to
be fl(nlogn).
Gossiping protocol for separate messages Every node v maintains a priority
queue Queue,, in its local memory. The queue is used to store the rumors that v
still needs to transmit. There is a set Received,, to store all the rumors learned
so far. A newly received message with a rumor that is not stored in Received,,
is added to both Received,, and Queue,,. The protocol working according to
these rules is called GossipSeparateMessages; it is given in Figure 5.4.
Let the nodes be ordered cyclically by their names in [0, n1], so that i is followed
by the number (z + l) mod n. This ordering governs which nodes transmit in any
75
initialize Received,, := Queue,, := {r};
for round i := 0 to oo do
if v = i (mod n) then
if Queue,, nonempty then
transmit the first rumor r in Queue,, and remove r from Queue,,
else
attempt to receive a message;
if rumor r received then
if r is not in Received,, then
insert r into Queue,, and add to Received,,
Figure 5.4: Protocol GossipSeparateMessages; code for node v.
RoundRobin type of a protocol, including GossipSeparateMessages in
particular.
The priority queue Queue,, has its own queuing discipline. Rumors are ordered
cyclically, starting from the owners input rumor r. This rumor is followed by
rumors with larger indices according to their order, that is, r+1, r+2, until rn_ 1,
which is then followed by r0, r 1, through the final rv_}.
Theorem 16 Protocol GossipSeparateMessages takes no more than
19nlgn of rounds on the average to complete gossiping on a network ofn nodes.
Proof: The full cycle of n rounds makes an epoch. During the first epoch,
every node v transmits its input rumor r. Every node transmits each rumor
exactly once. The worstcase time complexity of this gossiping protocol is n3,
because n epochs are sufficient to disseminate one rumor.
Take some rumor r and consider the event Â£a(r) which holds when r has been
transmitted by olgn different nodes. The probability of the event that some
node y has not heard r, conditional on Â£a(r), is n~a. The probability that some
node has not heard r, conditional on Â£a(r), is at most n n~a = nl~a. The
76
probability that some node has not heard some rumor, conditional on the events
Sa{r) for all rumors r, is at most n2~a. In the following application we will use
a = 3 to obtain the probability n2~3 = n_1.
Consider the following event B: every rumor was transmitted at least 3 lg n times
during the first 6 lgn epochs, for some fixed integer b to be determined later.
Take a node v and the blgn nodes preceding v in the cyclic ordering. If any
of these nodes receives rumor rv in the first epoch from v, then it transmits rv
in the first blgn epochs. When v transmits in the first epoch, then every other
node receives rv with the probability 1/2 independently over all the nodes. The
expected value of the number of these nodes that receive rv in the first epoch
is /r = lgn. Take 5 determined by the equality (1 <5) lgn = 3 lgn, that is,
5 = 1 . By the Chernoff bound (5.1), the probability that less than 3lgn
nodes receives the rumor rv in the first epoch is at most
exp{ ^1 ^ ^ lgn} < n_^1_^23lge .
Take an integer b > 6 for which the inequality (1 )2lge>3 holds. One can
check directly that b = 19 is sufficiently large. Such a b guarantees that event B
does not to hold with probability of at most n2.
Conditional on B, the expected time of gossiping is at most
bnlgn + n~2 n3 = n(l + 6lgn) ,
because the worstcase time complexity is n3. Since event B does not hold with
probability of at most n~2, the unconditional expected time complexity is at
most
n(l + 5lgn) + n~2 n3 = n(2 + feign) ,
for a similar reason.
The average number of rounds to complete gossiping on a network of n nodes
needs to be fl(nlogn). We obtain this as a corollary to a lower bound for m2a
communication given as Theorem 18 in Section 5.6.
5.6 Communication m2a with separate messages
We give a protocol of the 0(klog(n/k) logn) average time complexity. We start
with procedure M2ASeparate(/c) given in Figure 5.5, which is a solution of
77
the m2a communication task when k may be a part of code. The same notational
conventions and the understanding of the differences between procedures and
protocols are assumed as explained in the beginning of Section 5.4.
The ifthenelse instruction marked with (a) in M2 ASeparate (A;) in Figure 5.5
is referred to as subroutine SelectorSubroutine(21). This is because it
is very similar to the SelectorSubroutine(21) for the protocol with com
bined messages, described in Figure 5.2, in that it resorts to a (n, 2l)selector.
There are two differences in how the two versions of subroutine SELECTOR
SUBROUTINE^1) are used. The first difference in the current version is that
now after each round of SelectorSubroutine(21) we continue with Round
RobinStack for lOlgn rounds, while in the case of combined messages we in
sert lOlgn of RoundRobin rounds after every used (n, 2*)selector. The next
difference in the current version is that now a specific rumor needs to be selected
for each transmission by a node.
An auxiliary protocol RoundRobinStack used in procedure
M2ASeparate(A;) is defined as follows. A node maintains a stack of rumors
different from its original one. A rumor heard by the node is pushed on its stack.
A rumor to transmit is obtained by popping the stack; when the stack is empty,
then the node pauses. The stack is initialized to be empty, and is emptied just
before RoundRobinStack is to be continued for lOlgn rounds.
Protocol M2ASeparateMessages is given in Figure 5.6. Next we ana
lyze the average complexity and optimality of the protocol. Let m = [IgA:].
We show that the m2a communication task is completed by the end of M2A
SEPARATE(2m) with probability of at least 1 4k/n3. First we prove the fol
lowing invariant:
Lemma 12 By the call of SelectorSubroutine(2Â£), at most se
lected nodes have not broadcasted successfully with probability of at least 1
Y^=e 2n3, for the consecutive values of Â£ = m, l m 1, down to t = 0.
Proof: The proof of this invariant is by induction on the value of Â£, in the
decreasing order from Â£ = m down to Â£ = 0. The base of induction is pro
vided by considering the case of Â£ = m. Observe first that during Selector
SuBROUTiNE(2m) of M2ASEPARATE(2m), at most 2m_1 activated nodes do
not transmit as unique transmitters in the rounds of (a). These that transmit
as unique transmitters in some rounds (a), and there are at least 2m_1 of them,
78
for i := [IgA:] downto 0 do
for j := 1 to m(n, 2*) do
(a) if v Â£ Fj(n, 2l) then transmit rumor rv
else attempt to hear a message
{this is the jth round of SelectorSubroutine^)}
(r) continue RoundRobinStack in next lOlgn rounds
Figure 5.5: Procedure M2ASeparate(A;); the code for node v.
also perform successful broadcasts in the following lOlgn rounds of Round
RobinStack in code line (r), with probability of at least 1 1/n3 each, by
Lemma 11. This gives the probability estimate of 1 2 2m_1/n3 = 1 2m/n3.
To prove the inductive step, suppose that the invariant holds for some Â£, where
0 < Â£ < m, we show that it also holds for t 1. Conditional on the invari
ant holding true for Â£, at most 2e~l activated nodes do not transmit as unique
transmitters in rounds (a) during SelectorSubroutine(2^). Those nodes
that transmit as unique transmitters in rounds (a), and there are at least 2^_1
of them, complete broadcast during the next lOlgn rounds in line (r) of the
code with probability of at least 1 1/n3 each. Consequently, by the begin
ning of SelectorSubroutine(2^_1) at most 2e~x of activated nodes have not
complete broadcast, with probability of at least
Theorem 17 Protocol M2ASeparateMessages has the 0(k\og{n/k) logn)
average time complexity.
Proof: Let m= [IgA;]. Procedure M2ASEPARATE(2m) takes
m
m
a=Â£
which completes the proof.
m
^P(9(2llog(n/2l)lgn) = 0(k\og(n/k) logn)
i=o
79
for j = 0 to lgn do
call M2ASeparate(2j)
call GossipSeparateMessages
Figure 5.6: Protocol M2ASeparateMessages.
rounds, and during its execution the m2a communication task is completed with
probability of at least
1  2/n3 > 1 4k/n3 ,
a=0
by Lemma 12. The number of rounds taken by M2ASeparateMessages by
the end of execution of M2ASEPARATE(2m) is
m
^ 0(2 log(n/2) logn) = 0(k\og(n/k)\ogn) .
(2=0
The worstcase scenario results in time 0(n3), as argued in the proof of The
orem 16. It can occur with probability of at most Ak/n3. This justifies the
estimate
0{k log(n/k) logn) + 0(n3) Ak/n3 = 0(k log(n/k) log n)
to be an upper bound on the average time.
Next we show a lower bound for m2a communication with separate messages.
We begin with a technical lemma.
Lemma 13 Let a(z) be a positive integer, for i E X. Suppose b(i,v) are non
negative integers, such that a{i) > v)> for ^ T and v ^ V Then the
estimate
2b(i, v)'
n(
vev
1 
2>a{i)
()>i
) 3
holds for every i El.
80
Proof: Let us fix the positive integers a(i), for i e 1. The proof is by induction
on the size of set V. For V = 1 it holds since the product is at least 1
Suppose the product is always at least 1/3 if it is comprised of at most j > 1
factors. Consider V containing j + 1 elements. Multiply the jth and (j + l)th
factors together to obtain the number which is to be treated as one factor:
/ 2 b(i,z)\/ 2 b(i,w)\ 2 b(i,z) + b(i,w)
V 3a(i) J V 3a(i) / 3 a(i)
where z and w are the indices of the jth and (j+l)st original factors, respectively.
We obtain that
m 2 b(i,v)\ / 2 b{i,z)\ / 2 b(i,z)\ rr/ 2b{i,v)\
3a(i) J V 3a(i) J\ 3a{i) J 3a(i) J
b(i, z) + b(i, w)
a(i)
)n(i
v^w,z
2b(i, v)
3 a(i)
) (5.11)
Define (3(i, v) b(i, v), for v ^ w,z, and (3(i, w) < b(i, w) + b(i, z), which allows
to transform the equation (5.11) as follows:
b(i, z) + b(i, w)
a(i)
)n(i
v^w,z
2b(i, v)
3 a(i)
) n (i
vV\{z}
2 P(i,v)
3 a(i)
We have that V \ {z} is of a smaller size than V, and
= bv) 
uV\{z} nSV
Therefore (5.12) is at least 1/3 by the inductive assumption, which completes
the proof.
Theorem 18 The average number of rounds to complete gossiping on a network
of n nodes with k nodes initially activated is fl(klogn), by any m2a protocol for
the model of separate messages.
Proof: Let V be a m2a protocol. Let s = (lg32) k lg 18p~a n. We have
s < k\gn and s = Q(k log n). We will show that s rounds are not sufficient
to complete the m2a communication task by protocol V on random graph with
large probability.
81
Let Tj denote the set of nodes transmitting in round i in the course of an execu
tion of protocol V on random graph. Let a(i) = \Ti\. We partition all the rounds
up to s into two categories, depending on whether the inequality a(i) > 41gn
holds.
Claim: In first s rounds of protocol V no rumor is successfully delivered during
rounds i < s such that a{i) > 41gn or a(i) = 0, with probability at least
1 (lg n)/n.
Now we prove this claim. If a(i) = 0 then with probability 1 no rumor is sent,
thus also no one is delivered. Let i be a round with a(i) > 41gn and let w be a
node. The probability that w receives a message from a node in Zj at round i is
a(i) 1 a(i) 1
2 2W_1 2d) > n3
for a sufficiently large n. The probability of the event that some node receives
such a message at round i is smaller than 1/n2. The probability of the event
that some node receives such a message in the first s rounds is smaller than
s/n2. Hence the probability that no rumor is exchanged during the rounds we
consider is at least 1 s/n2 > 1 (lgn)/n. This completes the proof of the
Claim.
In the remaining part of the proof we analyze the progress in delivering rumors
during the rounds i < s such that 0 < a(i) < 4 lg n. Let i be such a round with
0 < a(i) < 41gn and let v 6 Tt. The probability that w receives the message
from node v at round i is at most 1/2^. Let c(i,v) denote the number of
activated nodes that in the beginning of round i still do not know rv. We have
c(i, v) < n since the total number of nodes without rumor rv is at most n 1 in
any round. We restrict our analysis to the rounds in which the additional bound
c(i,v) > 1801g2n holds, which covers the case when many nodes still remain to
learn rv. Define b(i,v) < a(i) to be the number of nodes that want to transmit
the rumor rv of v at round z, in the case when c(i, v) > 1801g2n holds, and let
b(i,v) = 0 otherwise. Note that J2vb(hv) ^ a(*) fr every number i.
Let w be a node without rumor rv in the beginning of round i. The probability
that w receives the rumor of v at round i is at most
Khv) , {i)_i b(i,v)
2 1 7 j 2W '
82
The expected number of nodes that receive the rumor rv of v for the first time
is at most c(i,v)b(i,v)/2aW; which means that the expected number of nodes
without the rumor of v is at least c(i,v)( 1 b{i,v)/2^).
We use the Chernoff bound to estimate the probability of the event
Let a trial result in success when a node w without rv receives it in round i.
Let the random variable X denote the number of successes over all the nodes
which do not have rv at the beginning of round i. The expected value of X is
c(i,v) b(i,v)/2W. Consider the parameter 5 = 1. Note that 8 > 1/3,
since 2a^/a(i) > 2. It follows that the number of nodes without rumor v
decreases after round i by a factor at most
b(i,v) 2 2aW 2 b(i,v)
2ab') 3 a(i) 3 a(i)
with probability of at least
C(.,)6(,,v)(2oa{0 jfo) > 1 _ 87)H^)6W3^) > 1 1/n3
by the Chernoff bound (5.2). Observe that is a decreasing function of
(l+<5) o
8 in the interval [1/3, oo), attaining (4/3)4e at 8 = 1/3 as its maximum value.
Also  > 3 lg n, since c(i,v) > 1801g2n and a(i) < 41gn.
Now we analyze the progress in delivering rumors during the first s rounds of
an execution of protocol V. We have
max{c(s + 1, v), 180 lg2 n}
> c(i,u) n(i 
i
2b(i, v)
3 a{i)
(5.13)
for every activated node v, since the factors under the product are equal to 1 for
i such that c(i, v) < 180 lg2 n. The inequality (5.13) holds with the probability of
at least 1 s 1/n3, since there are at most s rounds involved in equation (5.13)
and each factor in the product contributes to the product with probability at
least 1 1/n3. Note that (5.13) is equivalent to
2b(i,v)\ max{c(s + 1, v), 180lg2 n}
3a(i) ) ~~ n 1
n(i
i
83
since c(\,v) n 1. Consequently, with probability at least 1 k s/n3 >
1 s/n2, we have that
n (* ffer)  (5.14)
i ii ' ' ' ' n
where the product is taken over all k activated nodes v and over allz < s. On
the other hand, by Lemma 13 we obtain the estimates
IK*
2b(i,v)\ > 1_ > /180lg2n\fc
3a(i) J ~~ 3s \ n 1 /
(5.15)
Combine the estimates (5.14) and (5.15) to obtain that there is at least one
activated node v such that c(s + l,v) > 1801g2n, with probability at least
1 s/n2. Therefore protocol V requires more than s rounds with probability of
at least 1 (lgn)/n2, and hence its expected running time is at least s(l
(lgn)/n2) > s/2 = fl(klogn).
Corollary 1 For any gossiping protocol for the model of separate messages, the
average number of rounds to complete gossiping on a network of n nodes is
fl(nlogn).
Proof: Follows from Theorem 18 by substituting n for k.
Protocol M2ASeparateMessages is within factor of at most C?(log(n/A;))
close to optimality, by Theorems 17 and 18. In the case of k = O(n), which
includes gossiping, the protocol is asymptotically optimal.
84
6. Lower bounds on
gossiping
The results given in this Chapter are a joint work with Bogdan Chlebus, see [28].
6.1 Introduction
We consider lower bounds on gossiping in radio networks in different settings
and for different classes of protocols. The model of radio network is adhoc.
Each of n nodes has assigned unique id from range [nc] where c > 1 is constant.
We say that network is of large labels if c > 1. Nodes are synchronized by
global round number. Transitions are executed in rounds. Node can transmit
one packet per round. Transmission from a node reaches all its outneighbors in
the same round. Node v successfully receives transmission from its inneighbor
u in a round if and only if u is the only transmitting inneighbor of v in this
round. If there are at least two inneighbors of v transmitting in the same round
then collision occurs and messages cannot be successfully received.
We consider two classes of protocols oblivious and adaptive. Deterministic obliv
ious protocol can be defined following way. Node v running deterministic obliv
ious protocol decides about its transmission in round i based on round number
i, its id and size of the network n. The history of previously received messages
is irrelevant. Deterministic oblivious protocol can be also represented as fixed
schedule of transmissions (T0,... ,Tm) where Tj C [nc] and 0 < i < m is the
round number. In round i all nodes that belong to set T* transmit. Each node
can compute its schedule of transmissions based on its id and network size n.
The simplest example of deterministic oblivious gossiping protocol is Round
Robin. Randomized oblivious gossiping protocol is an extension of deterministic
one. In round i each node v transmits with probability Pi(v) where pl(v) depends
on round number i and id(v). As opposed to oblivious protocols adaptive one
can be thought as class of protocols adjusting to the network structure. Node
v running adaptive protocol decides about its transmission in round i based on
round number i, its id, size of the network n and history of received messages
up to round i 1. The contents of the transmitting packet is also determined
by round number i, id of the node, size of the network n and history of received
messages.
85
We consider two communication tasks: gossiping and leader election. In the
gossiping problem each node contains a rumor to be disseminated to all other
nodes. Gossiping is completed when all nodes learn all rumors. In the leader
election problem all nodes start execution in state I am not the leader. Leader
election is completed when there is exactly one node in state I am the leader
and the rest of the nodes is in state I am not the leader. The leader election
problem makes sense only in the model of large labels. If the range of labels is [n]
then node v with id(v) 0 can become a leader automatically. Historically the
problem of leader election in radio networks arose from the gossiping. The prob
lem of gossiping in symmetric graph in which nodes know their neighborhoods
can be completed following way. Leader issues token which traverses graph in
DFS manner. Token collects all rumors. Second DFS traversal broadcasts all
the rumors.
Gossiping problem can be considered in the model of combined messages and
in the model of separate messages. In the model of combined messages node
can include all its rumors into one packet. In the model of separate messages
only one rumor can be transmitted in a packet. We assume model of combined
messages unless stated otherwise.
Our results and previous work. The model of oblivious gossiping was intro
duced by Chlebus, Gqsieniec, Lingas, and Pagourtzis [19]. Authors showed that
for each deterministic oblivious gossiping protocol there exists directed network
which requires Q(n2) rounds. For symmetric networks authors presented deter
ministic protocol that runs in time 0{n3/2) on any nnode radio network. This
protocol is optimal as shown by Kowalski and Pelc [65]. In [19] authors presented
Las Vegas randomized oblivious protocol which runs in expected time 0(n2) in
case of directed networks and 0(nlog2 n) in case of symmetric networks. We can
see that randomization improves time of oblivious gossiping significantly in case
of symmetric networks from 0(n3/2) to 0(n log2 n). We will show that in case
of directed networks randomized protocol cannot beat deterministic one. We
will show that any Las Vegas randomized oblivious gossiping protocol requires
expected time fl(n2). The best previously known lower bound for randomized
oblivious gossiping protocol was fi(n) as shown by Kowalski and Pelc [65]. Our
bound is tight since RoundRobin protocol is the special case of Las Vegas
randomized oblivious gossiping protocol and works in expected time 0(n2). We
will show that any Monte Carlo randomized oblivious gossiping protocol that
errors with constant probability requires expected time Q(n2) for some difficult
86
network.
In class of adaptive protocols we show that each adaptive gossiping protocol
working in the model of large labels requires ft(nlogn) rounds. This result is
also extended to leader election protocols.
The best previously known lower bound for these problems was n due to nnode
star. Our lower bound for gossiping protocol is almost tight in case of symmetric
networks due to upper bound 0(n log3 n) as shown by Gqsieniec, Pagourtzis, and
Potapov [44], In case of directed networks the best known gossiping protocol
works in time 0(n4/3 log4 n) as shown by Gqsieniec, Radzik, and Xin [49]. The
best know upper bound for leader election problem is 0(n\og3n) as shown by
Chrobak, Gqsieniec, and Rytter [31]. Thus our lower bound is almost tight for
leader election problem.
The model of separate messages was considered by Clementi, Monti, Silvestri
[34]. Authors presented deterministic oblivious gossiping protocol which runs in
time 0(n2) in case of directed and symmetric networks. The adaptive gossiping
in directed graphs requires fl(n2) rounds as shown by Gqsieniec and Potapov
[47]. Thus protocol presented by Clementi, Monti, Silvestri [34] is optimal in
case of directed networks. We will show that this protocol is also optimal in
class of oblivious gossiping protocols working on symmetric graphs.
Structure of this chapter. In section 6.2 we show lower bound Q,(n2) on
expected running time of Las Vegas oblivious randomized gossiping protocol.
This result also holds for Monte Carlo protocols. Next in section 6.3 the lower
bound Q(n\ogn) is shown for adaptive deterministic gossiping protocol with
large labels and deterministic leader election problem. The last result lower
bound Q(n2) on deterministic oblivious gossiping in symmetric graph for the
model of separate messages in shown in section 6.4.
6.2 Randomized oblivious gossiping
We consider lower bound on oblivious randomized gossiping with combined mes
sages. We will show that any Las Vegas oblivious randomized gossiping protocol
requires expected time Q,(n2). Next we will show that similar result holds for
Monte Carlo protocols.
The network of nnodes consist of vertices {u0,..., un_i}. Each node v has
assigned its unique id(v) E [n]. Each node u, contains a rumor r* to be dissem
87
id(v0)=0
id(v1)=l
id(vn ,)=nl
Figure 6.1: Example of return graph G(n, 7r) in which permuta
tion 7r is identity.
inated. Oblivious randomized gossiping is defined by fixed schedule of trans
missions (T0,...,Tm) where 7] = (pl0,... ,pln_i) and p\ is the probability of
transmission of node vk in round i. Transmitting node includes all rumors it
learnt to its packet.
Let return graph G(n, n) be the network of nnodes constructed following way.
Let V = {u0,..., un_i} be the set of nodes of the network. There is an edge
between each pair Vj Uj+i for i = 0,..., n 2. There are return edges w, < Vj
for j = 1,..., n 1 and i < j. Function n is a permutation of [n] and provides
labeling of the nodes that is id(vi) = n(i). The example of return graph with
permutation ir equal to identity is depicted on Figure 6.1.
For simplicity we assume that node v successfully receives a packet provided no
collision at v and v does not transmit. The proof can be extended to the classical
model when v receives message when no collision at v and v can transmit. The
only difference between these two models is in constant factor.
In our proof we will use the Yaos minimax principle that can be formulated as
the following fact:
Fact 1 ([78]) Let P be a probability distribution over the set of inputs. Let A
denote the set of all deterministic algorithms. For A Â£ A let C{A, P) denote the
expected running time of A over P. Let 1Z be the set of randomized Las Vegas
algorithms and let E(R, I) denote the expected running time of R Â£ 7Z on input
I. Then for all P and all R Â£71,
min C(A, P) < max E(R, I)
AeA i
Lemma 14 Let QV be the deterministic oblivious gossiping protocol. Then QV
has to guarantee that each label transmits as singleton.
88
Proof: Let us assume contrary that some label i does not transmit as singleton.
Let us take G{n, 7r) in which 7r(0) = i that is id(v0) = i. Then node no never
passes its rumor to vx. Thus QV never completes gossiping in G(n, ir).
Theorem 19 For any Las Vegas randomized oblivious gossiping protocol, there
exists a directed network G such that the protocol requires the expected time
(n l)2 ft
v 4' on G.
Proof: Let QV be any deterministic oblivious gossiping protocol. Let proba
bility distribution P over the directed graphs of n nodes will be defied following
way. Each graph G(n, n) is equally likely to be drawn and remaining graphs are
drawn with probability 0. Thus probability of drawing G(n, n) is equal to
Let random variable X be time that takes xq to move from no to un_i in QV.
Let random variable Xi be the time that xq waits to move from node Vi to vi+x.
We can see that X = Xq + ... + Vn_2. Let us consider rumor Xq in node v0.
By lemma 14 protocol QV minimizes expected time of sending r0 from vq to v\
provided first n transmissions (T0,..., Tki) is a permutation of [n]. Probability
that Vq successfully transmits its rumor in round 0 < j < n 1 is at most 1/n.
Thus the expected time to pass rumor from v0 to vx is
n1
E(V)>Â£j =
3=0
n 1
2
. We can extend this inference for following nodes u*. Thus we have
ni1
E(Vi) > y 3 =
n 1
n
3=0
and hence
E(X) > g
>
(n ~ l)2
4
t=0
By Fact 1, each Las Vegas randomized oblivious protocol requires average time
fl(n2) for some network.
Theorem 20 Let QV be some Monte Carlo randomized oblivious gossiping pro
tocol that errors with some constant probability 0 < e < . Then QV requires
expected time for some network G.
89
