B.S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc, W. Rytter,
Deterministic broadcasting in ad hoc radio networks,
*Distributed Computing* 15 (2002), 27-38.

Preliminary version appeared in: Proc. 11th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'2000), San Francisco, USA, January 2000, 861-870.

Abstract:

We consider the problem of distributed deterministic broadcasting in
radio networks of unknown topology and size.
The network is synchronous.
If a node *u* can be reached from two nodes which
send messages in the same round, none of the messages is received by *u*.
Such messages block each other and node *u* either hears the noise of
interference of messages, enabling it to detect a *collision*, or does not
hear anything at all, depending on the model.
We assume that nodes are completely ignorant of the network: they
know neither its topology, nor size, nor even their immediate neighborhood.
The initial knowledge of every node is limited to
its own label. We study the time of deterministic broadcasting under this
total ignorance scenario.
Previous research has concentrated on distributed randomized broadcasting
algorithms working for unknown networks, and on deterministic
off-line broadcasting algorithms assuming full knowledge of the radio network.
Ours are the first
broadcasting algorithms simultaneously distributed and deterministic,
that work for arbitrary totally unknown radio networks.
The results for the model without collision detection:
We develop a linear-time broadcasting algorithm for symmetric graphs,
which is optimal.
For arbitrary *n*-node graphs, we prove a lower bound
*Omega(D log n)*,
where *D* is the diameter, and develop an algorithm working in time
*O(n ^{11/6})*. Next we show that broadcasting with acknowledgement is not possible
in this model at all.
For the model with collision detection,
we develop efficient algorithms for broadcasting and for
acknowledged broadcasting in strongly connected graphs.

A. Dessmark, A. Pelc,
Deterministic radio broadcasting at low cost, *Networks* 39 (2002), 88-97.

Preliminary version appeared in: Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001), February 2001, Dresden, Germany, LNCS 2010, 158-169.

Abstract:

We consider the problem of distributed deterministic broadcasting in radio
networks. The network is synchronous. A node receives a message in a given
round iff exactly one of its neighbors transmits. The source message has to
reach all nodes. We assume that nodes do not know network topology or even
their immediate neighborhood. We are concerned with two efficiency measures
of broadcasting algorithms: its execution *time* (number of rounds),
and its *cost* (number of transmissions). We focus our study on
execution time of algorithms which have cost close to minimum.

We consider two scenarios depending on whether nodes know or do not know
global parameters of the network: the number *n* of nodes and the eccentricity
*D* of the source.
We show that the minimum cost of broadcasting
in an *n*-node network of unknown topology is *n*, if at least one of the
above parameters is unknown, and it is *n-1*, if both of them are known.
Our main contribution are lower bounds on time of low-cost broadcasting
which show sharp differences between these scenarios. We show that if nodes
know neither *n* nor *D* then any broadcasting algorithm whose cost exceeds
the minimum by *O(n ^{b} )*, for any constant

In addition, we show that very fast broadcasting algorithms must have high
cost. We prove that every
broadcasting algorithm that works in time *O(nt(n))*, where *t(n)*
is polylogarithmic in *n*,
requires cost
*Omega (n log n / log log n)*.
Since the fastest known broadcasting algorithm
works in time *O (n log ^{2} n)*, its cost (as well as the
cost of any faster broadcasting algorithm, if it exists) must be
higher than linear.

A. Pelc,
Searching games with errors - Fifty years of coping with liars,
*Theoretical Computer Science* 270 (2002),
71-109.

Abstract:

This is a survey on searching with errors considered in the framework of two-person games.
The *Responder* thinks of an object in the search space, and the *Questioner*
has to find it by asking questions to which the Responder provides answers, some of which
are erroneous. We give a taxonomy of such games, depending on the type of questions allowed,
on the degree of interactivity between the players, and on the imposed limitations on errors.
We survey the existing results concerning such games, concentrating on the issue of optimizing
the Questioner's querying strategy, and pointing out open problems. We show the relations
between searching games with errors and problems concerning communication through a noisy
channel and error-correcting codes. Finally, we discuss other search and computation
problems with faulty feedback which are related to searching with errors.

K. Diks, E. Kranakis, D. Krizanc, A. Pelc,
The impact of information on broadcasting time in linear radio networks,
*Theoretical Computer Science* 287 (2002), 449-471.

Preliminary version appeared as:

K. Diks, E. Kranakis, D. Krizanc, A. Pelc, The impact of knowledge on broadcasting time in radio networks, Proc. 7th Annual European Symposium on Algorithms, ESA'99, Prague, Czech Republic, July 1999, LNCS 1643, 41-52.

Abstract:

We consider the problem of distributed deterministic broadcasting in radio
networks whose nodes are located on a line.
Nodes send messages in synchronous time-slots. Each node *v* has a
given transmission range.
All nodes located within this range can receive messages from *v*. However,
a node situated in the range of two or more nodes that
send messages simultaneously,
cannot receive these messages and hears only noise. Each node knows only its
own position and range, as well as the maximum of all ranges.
Broadcasting is adaptive: Nodes can decide on the
action to take on the basis of previously received messages, silence or noise.
We prove lower bounds on broadcasting time in this model and construct
broadcasting protocols whose performance nearly matches these bounds for
the simplest case when nodes are situated on a line. We also show that if
nodes do not even know their own range, every broadcasting protocol must
be hopelessly slow.
While distributed randomized broadcasting algorithms, and, on the other hand,
deterministic off-line broadcasting algorithms assuming full knowledge of the radio network,
have been extensively studied in the literature, ours are the
first results concerning broadcasting algorithms that are distributed and
deterministic at the same time. We show that in this case, information
available to nodes influences the efficiency of broadcasting
in a significant way.