A. Pelc, Activating anonymous ad hoc radio networks,
*Distributed Computing* 19 (2007), 361-371.

Preliminary version appeared as:

A. Pelc, Waking up anonymous ad hoc radio networks, Proc. 19th International Symposium on Distributed Computing (DISC 2005), September 2005, Cracow, Poland, LNCS 3724, 260-272.

Abstract:

We consider the task of activating an anonymous ad hoc radio network from a single source, by a deterministic algorithm.
In the beginning only the source is active and has to activate other nodes by disseminating messages throughout the network.
Nodes of the network do not know its topology and they do not have distinct labels. In such networks
some nodes are impossible to reach. A node in a network is *accessible* if it can be activated by
some (possibly network-dependent) deterministic algorithm. We show that the problem of recognizing whether a given node
of an anonymous radio network is accessible, can be solved in polynomial time for the synchronous scenario.
A deterministic wakeup algorithm
for ad hoc networks is *universal* if it activates
all accessible nodes in all networks. We study the question of the existence of such a universal activating algorithm.
For synchronous communication we design a universal activating algorithm, and for asynchronous communication we show that
no such algorithm exists.

A. Pelc, D. Peleg, Feasibility and complexity of broadcasting with random transmission failures,
*Theoretical Computer Science* 370 (2007), 279-292.

Preliminary version appeared in:

Proc. 24th Ann. ACM Symposium on Principles of Distributed Computing (PODC'2005), July 2005, Las Vegas, U.S.A., 334-341.

Abstract:

Fault-tolerant broadcasting in the message passing and radio models
is considered under a probabilistic failure model.
At each step, the transmitter of each node may fail with fixed
constant probability *p<1*, and failures are independent.
Both node-omission and malicious transmission failures are studied.
Our goal is to establish conditions on feasibility and to estimate the
(synchronous) time complexity of almost-safe broadcasting
(i.e., broadcasting which is correct with probability at least
*1-1/n* for *n*-node graphs and for sufficiently large *n*)
under these scenarios.

D. Kowalski, A. Pelc, Optimal deterministic broadcasting in known topology radio networks,
*Distributed Computing* 19 (2007), 185-195.

Abstract:

We consider deterministic broadcasting in radio networks whose nodes have full
topological information about the network.
The aim is to design a
polynomial algorithm, which,
given a graph *G* with source *s*, produces a fast broadcast scheme in the radio
network represented by *G*.
The problem of finding a fastest broadcast scheme for a given graph is NP-hard, hence it is only
possible to get an approximation algorithm.
We give a deterministic polynomial algorithm which produces a broadcast scheme of length
*O(D + log ^{2} n)*, for every

J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc,
Searching for a black hole in synchronous tree networks,
*Combinatorics, Probability & Computing* 16 (2007), 595-619.

Preliminary version appeared as:

J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc, Searching for a black hole in tree networks, Proc. 8th International Conference on Principles of Distributed Systems (OPODIS'2004), December 2004, Grenoble, France, LNCS 3544, 67-80.

Abstract:

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous tree network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable of identifying a black hole is two. For a given tree and given starting node we are interested in the fastest possible black hole search by two agents. For arbitrary trees we give a 5/3-approximation algorithm for this problem. We give optimal black hole search algorithms for two ``extreme'' classes of trees: the class of lines and the class of trees in which any internal node (including the root which is the starting node) has at least 2 children.

A. Dessmark, A. Pelc, Broadcasting in geometric radio networks,
*Journal of Discrete Algorithms* 5 (2007), 187-201.

Preliminary version appeared as:

A. Dessmark, A. Pelc, Tradeoffs between knowledge and time of communication in geometric radio networks, Proc. 13th Ann. ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001), Crete, Greece, 59-66.

Abstract:

We consider deterministic broadcasting in *geometric radio networks*
(GRN) whose nodes
know only a limited part of the network. Nodes of a GRN are situated in the
plane and each of them is equipped with
a transmitter of some range *r*. A signal from this node can reach all nodes
at distance at most *r* from it but if a node *u* is situated within the range of
two nodes transmitting simultaneously, then a collision occurs at *u* and *u* cannot get any message.
Each node knows the part of the network within *knowledge radius* *s* from it, i.e., it
knows the positions, labels and ranges of all nodes at distance at most *s*.
The aim of this paper is to study the impact of knowledge radius *s* on the
time of deterministic broadcasting in a GRN with *n* nodes
and eccentricity *D*
of the source. Our results show sharp
contrasts between the efficiency of broadcasting in geometric radio networks
as compared to broadcasting in arbitrary graphs.
They also show quantitatively the impact of various types of knowledge
available to nodes on broadcasting time in GRN.
Efficiency of broadcasting is influenced by knowledge radius, knowledge of individual
positions when knowledge radius is zero, and awareness of collisions.

J. Czyzowicz, E. Kranakis, D. Krizanc, A. Pelc, M. Vargas Martin,
Assigning bookmarks in perfect binary trees,
*Ars Combinatoria* 82 (2007), 165-179.

Abstract:

Consider a web domain consisting of a collection *V={v_1,...,v_n}*
of web pages connected by hyperlinks.
Assume that there exists a directed path of hyperlinks from the
home page *r* to any other page of the collection. Let *p_i* be
the probability that a user wants to access page *v_i*. A *bookmark*
is an additional hyperlink from the home page *r* to any other page.
We want to add *k* bookmarks to this web page collection, so as to minimize
the expected access time from *r*, measured by the length of the shortest
path of hyperlinks. We show that this optimization problem is
NP-hard in general, even for uniform probability distribution, and solve it
polynomially in two cases: when the web domain is a line with
arbitrary probability distribution, and when the domain is a complete
binary tree with uniform distribution and *k < sqrt{n+1}*.

E. Markou, A. Pelc, Efficient exploration of faulty trees,
*Theory of Computing Systems* 40 (2007), 225-247.

Preliminary version appeared in:

Proc. 15th Australasian Workshop on Combinatorial Algorithms (AWOCA'2004), July 2004, Ballina Beach Resort, New South Wales, Australia, 52-63.

Abstract:

We consider the problem of exploration of trees, some of whose edges are faulty. A robot,
situated in a starting node and unaware of the location of faults,
has to explore the connected fault-free component of this node
by visiting all its nodes. The *cost* of the exploration is the number of edge traversals.
For a given tree and
given starting node, the *overhead* of an exploration algorithm is the worst-case ratio
(taken over all fault configurations)
of its cost to the cost of an optimal algorithm which knows where faults are situated.
An algorithm, for a given tree and given starting node,
is called *perfectly competitive* if its overhead is the smallest among
all exploration algorithms not knowing the location of faults.
We design a perfectly competitive exploration algorithm for any line,
and an exploration algorithm for any tree, whose overhead is at most 9/8 larger than that
of a perfectly competitive algorithm.
Both our algorithms are fairly
natural and the total time of local computations used during exploration is linear in the size of the
explored tree. Our main contribution is the analysis of performance of these algorithms, showing that
natural exploration strategies perform well in faulty trees.

S. Guilbault, A. Pelc, Fast adaptive diagnosis with a minimum number of tests, Proc. 18th International Symposium on Algorithms and Computation (ISAAC 2007), December 2007, Sendai, Japan, LNCS 4835, 415-426.

Abstract:

We study adaptive system-level fault diagnosis for multiprocessor systems.
Processors can test each other and later tests can be scheduled
on the basis of previous test results. Fault-free
testers correctly identify the fault status of tested processors, while
faulty testers can give arbitrary test results. The goal is to identify
correctly the status of all processors, assuming that the number of faults
does not exceed a given upper bound *t*, where *n* is the number of processors.
Tests involving disjoint pairs of processors can be performed simultaneously in one round.
Two most important measures of quality of a diagnosis algorithm are its worst-case cost (the number
of tests used) and time (the number of rounds used). It is known that the optimal worst-case cost of a
diagnosis algorithm is *n+t-1*. However, the known algorithms of this cost use time *Theta (n)*.
We present an algorithm with optimal cost *n+t-1* using time *O(log t)*, provided that the
upper bound *t* on the number of faults satisfies *t(t+1) < n+1*.
Hence, for moderate numbers of faults which we assume, our algorithm achieves exponential speed-up,
compared to the previously known diagnosis algorithms of optimal cost.