D. Kowalski, A. Pelc,
Broadcasting in undirected ad hoc radio networks,
*Distributed Computing* 18 (2005), 43-57.

Preliminary version appeared in:

Proc. 22nd Ann. ACM Symposium on Principles of Distributed Computing (PODC'2003), July 2003, Boston, U.S.A., 73-82.

Abstract:

We consider distributed broadcasting in radio networks,
modeled as undirected graphs, whose nodes have no information
on the topology of the network, nor even on their immediate neighborhood.
For randomized broadcasting, we give
an algorithm working in expected time *O (D log(n/D) + log ^{2} n)*
in

P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, D. Peleg,
Graph exploration by a finite automaton,
*Theoretical Computer Science* 345 (2005), 331-344.

Preliminary version appeared in:

Proc. 29th International Symposium on Mathematical Foundations of Computer Science (MFCS'2004), August 2004, Prague, Czech Republic, LNCS 3153, 451-462.

Abstract:

A finite automaton, simply referred to as a *robot*, has to
explore a graph whose nodes are unlabeled and whose edge ports are
locally labeled at each node. The robot has no a priori knowledge of
the topology of the graph or of its size. Its task is to traverse
all the edges of the graph. We first show that, for any *K*-state
robot and any *d>2*, there exists a planar graph of maximum
degree *d* with at most *K+1* nodes that the robot cannot
explore. This bound improves all previous bounds in the
literature. More interestingly, we show that, in order to explore
all graphs of diameter *D* and maximum degree *d*, a robot needs
*Omega(D log d}* memory bits, even if we restrict the exploration
to planar graphs. This latter bound is tight. Indeed, a simple DFS
up to depth *D+1* enables a robot to explore any graph of diameter *D*
and maximum degree *d* using a memory of size *O(D log d)* bits. We
thus prove that the worst case space complexity of graph exploration
is *Theta(D log d)* bits.

J. Czyzowicz, W. Fraczak, A. Pelc,
Transducers with set outputs,
*Journal of Automata, Languages and Combinatorics* 10 (2005), 37-49.

Preliminary version appeared in:

Proc. 8th Annual International Computing and Combinatorics Conference (COCOON 2002), Singapore, August 2002, 300-309.

Abstract:

We consider transducers with set output, i.e., finite state
machines which produce a set of output symbols upon reading any
input symbol. When a word consisting of input symbols is read, the
union of corresponding output sets is produced. Such transducers
are instrumental in some important data classification tasks, such
as multi-field packet classification. Two transducers are called
*equivalent* if they produce equal output upon reading any
input word. In practical data classification applications, it is
important to store in memory only one transducer of every
equivalence class, in order to save memory space. This yields the
need of finding, in any equivalence class, one transducer, called
*canonical* which is easy to compute, given any transducer from
this class. One of the results of this paper is the construction of
an algorithm which completes this task. Assuming that the input and
output alphabets are of bounded size, for a given *n*-state
transducer *T*, our algorithm finds the canonical transducer
*T'* equivalent to *T* in time *O(n log n)*.

A. Pelc, D. Peleg,
Broadcasting with locally bounded Byzantine faults,
*Information Processing Letters* 93 (2005), 109-115.

Abstract:

We consider broadcast in the presence of Byzantine node failures,
under the *t*-locally bounded model:
at most *t* faults are allowed in the neighborhood of every node.
This problem was considered for specific ``geometric'' graphs by Koo,
while we study it in the context of arbitrary graphs.
We first establish an upper bound on *t* for which a simple
broadcast algorithm proposed by Koo, the Certified Propagation
Algorithm (CPA), works correctly for arbitrary graphs,
under the *t*-locally bounded scenario, and a lower bound
on *t* for which no broadcast algorithm can work.
Since CPA does not use any global knowledge of network topology,
both these results hold regardless of whether the topology of the network
is known or if the network is ad hoc.
The situation when *t* is between these bounds turns out
to be quite complex. On the one hand we show a graph for which
CPA still works, and on the other hand we show a graph for which
CPA does not work but some other broadcast algorithm does.
The algorithm in the second example is an extension of CPA by a rule similar
to that in Dolev's Purifying Algorithm, and it requires knowledge
of the topology of the graph.
Knowledge of topology turns out to be essential in our context.
The separation between broadcast algorithms knowing the topology of the network
and ad hoc algorithms is evidenced by the following result:
there exists a graph for which some 1-locally fault-tolerant algorithm
exists, if the knowledge of the graph is assumed but
no such algorithm exists otherwise.

D. Kowalski, A. Pelc,
Time complexity of radio broadcasting: adaptiveness vs. obliviousness and
randomization vs. determinism,
*Theoretical Computer Science* 333 (2005), 355-371.

Preliminary version appeared in:

Proc. 10th Colloquium on Structural Information and Communication Complexity (SIROCCO 2003), June 2003, Umea, Sweden, 195-210.

Abstract:

We consider the time of broadcasting in ad hoc radio networks modeled as undirected graphs.
In such networks, every node knows only its own label and a linear bound on the number of nodes
but is unaware of the topology
of the network, or even of its own neighborhood. Our aim is to study
to what extent the availability of two important
characteristics of a broadcasting algorithm influences optimal broadcasting time. These characteristics
are adaptiveness and randomization.
Our contribution is establishing upper and lower bounds on
optimal broadcasting time for
three classes of algorithms: adaptive deterministic, oblivious randomized and oblivious deterministic.
In two cases we present tight bounds, and in one
case a small gap remains.
We show that for deterministic adaptive algorithms
time *Omega (n)* is required even for *n*-node networks of constant diameter.
This lower bound is strongest
possible, since linear time algorithms are known, and hence establishes optimal time *Theta (n)* for this class.
For oblivious randomized
algorithms we show an upper bound *O(n min{D, log n})* and a lower bound *Omega (n)*
on optimal expected broadcasting time in *n*-node networks of diameter
*D*. Finally, for oblivious deterministic algorithms we show matching upper and lower bounds
*Theta(n min{D, sqrt{n}})* on optimal broadcasting time.
Our results imply that enforcing obliviousness has at least
as strong negative
impact on broadcasting time
as enforcing determinism, and that algorithms having both these features
are strictly less efficient than those having only one of them.