L.M. Kirousis, E. Kranakis, D. Krizanc, A. Pelc, Power consumption in packet radio networks,
*Theoretical Computer Science* 243 (2000), 289-305.

Preliminary version appeared in: Proc. 14th Symposium on Theoretical Aspects of Computer Science, STACS'97, Lubeck, Germany, February/March 1997, LNCS 1200, pp. 363-374.

Abstract:

In this paper we study the problem of assigning transmission ranges
to the nodes of a multi-hop packet radio
network so as to minimize the total power
consumed under the constraint that adequate power is provided to
the nodes to ensure that the network is strongly connected
(i.e., each node can communicate along some path in the network
to every other node). Such assignment of transmission ranges is called complete. We also consider the problem of achieving
strongly connected bounded diameter networks.
For the case of *n+1* colinear points at unit distance apart (the unit chain)
we give a tight asymptotic bound for the minimum cost of a range
assignment of diameter *h* when *h* is a fixed constant and
when *h < (1+e) log n*, for some constant *e >0*.
When the distances between the colinear points are arbitrary, we
give an *O(n ^{4})* time dynamic programming
algorithm for finding a minimum cost complete
range assignment.

K. Diks, A. Pelc,
Optimal adaptive broadcasting with a bounded fraction of faulty nodes,
*Algorithmica* 28 (2000), 37-50..

Preliminary version appeared in:

Proc. Fifth Annual European Symposium on Algorithms, ESA'97, Graz, Austria, September 1997, LNCS 1284, pp. 118-129.

Abstract:

We consider broadcasting among *n* processors, *f* of which can be faulty.
A fault-free processor, called the source, holds a piece of information
which has to be transmitted to all other fault-free processors.
We assume that
the fraction *f/n* of faulty processors is bounded by a constant *\gamma<1*.
Transmissions are fault
free. Faults are assumed of *crash* type: faulty processors do not send
or receive messages. We use the {\em whispering} model: pairs of
processors communicating in one round must form a matching. A fault-free
processor sending a message to another processor becomes aware of whether
this processor is faulty or
fault free and can adapt future transmissions accordingly. The main result
of the paper is a broadcasting algorithm working in *O(log n)* rounds
and using *O(n)* messages of logarithmic size, in the worst case.
Our method
also gives the first algorithm for adaptive distributed fault diagnosis
in *O(log n)* rounds.

P. Panaite, A. Pelc,
Optimal broadcasting in faulty trees,
*Journal of Parallel and Distributed Computing* 60 (2000), 566-584.

Preliminary version appeared as:

P. Panaite, A. Pelc, Optimal fault-tolerant broadcasting in trees, Proc. 8th Annual International Symposium on Algorithms and Computation, ISAAC'97, Singapore, December 1997, LNCS 1350, pp. 143-152.

and

P. Panaite, A. Pelc, Universally fault-tolerant broadcasting in trees, Proc. International Conference on Parallel and Distributed Systems, ICPADS'97, Seoul, Korea, December 1997, pp. 724-729.

Abstract:

We consider broadcasting a message from one node of a tree to all other nodes.
In the presence of up to *k* link failures the tree becomes disconnected,
and only nodes in the connected component *C* containing the source
can be informed.
The maximum ratio between the time used by a broadcasting scheme *B* to
inform *C* and
the optimal time to inform *C*, taken over all components *C* yielded
by configurations of at most *k* faults, is the *k-vulnerability* of *B*.
This is the maximum slowdown incurred by *B* due to the lack of *a priori*
knowledge of fault location, for at most *k* faults.
This measure of fault-tolerance is similar to the
competitive factor of
on-line algorithms: in both cases, the performance of an algorithm
lacking some crucial information is compared to the performance of an
``off-line'' algorithm, one that is given this information as input.
It is also the first known tool to measure and compare fault-tolerance of
broadcasting schemes in trees.
We seek broadcasting schemes with low vulnerability, working for tree networks.
It turns out that schemes that give the best broadcasting time in a fault-free
environment may have very high vulnerability,
i.e., poor fault-tolerance, for some trees.
The main result of this paper is an algorithm that, given an arbitrary tree *T*
and an integer *k*, computes a broadcasting scheme *B* with lowest possible
*k*-vulnerability among all schemes working for *T*. Our algorithm has running
time *O(kn ^{2}+n^{2}log n)*, where

P. Denejko, K. Diks, A. Pelc, M. Piotrow,
Reliable minimum finding comparator networks,
*Fundamenta Informaticae* 42 (2000), 235-249.

Preliminary version appeared in:

Proc. 19th Int. Symp. Mathematical Foundations of Computer Science MFCS-94, Kosice, Slovakia, August 1994, LNCS 841, pp. 306-315.

Abstract:

we consider the problem of constructing reliable minimum finding networks built
from unreliable comparators. In case of a faulty comparator inputs are directly output without
comparison. Our main result is the first nontrivial lower bound on depths of networks
computing minimum among *n>2* items in the presence of *k>0* comparators.

E. Kranakis, A. Pelc,
Better adaptive diagnosis of hypercubes,
*IEEE Transactions on Computers* 49 (2000), 1013-1020.

Abstract:

We consider the problem of adaptive fault diagnosis
in hypercube multiprocessor systems.
Processors perform tests on one another 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 the hypercube dimension.
We propose an adaptive diagnosis algorithm whose efficiency is
drastically better
than that of any previously known strategies. While the worst-case
number of tests for
any of them exceeds *2 ^{n} log n* for an

P. Panaite, A. Pelc,
Impact of topographic information on graph exploration efficiency,
*Networks*, 36 (2000), 96-103.

Abstract:

A robot has to explore an undirected connected graph by visiting all its nodes and traversing all edges. It may either have a complete a priori knowledge of the graph, or only have an unoriented map of it, or finally, lack any knowledge of the graph. We study the impact of this varying amount of knowledge on exploration performance. It is shown that the best exploration algorithm lacking any knowledge of the graph uses twice as many edge traversals in the worst case as the best algorithm which has an unoriented map of the graph. On the other hand, the latter uses twice as many edge traversals in the worst case as the best algorithm having a complete knowledge of the graph. Similar results for the restricted case of exploration algorithms working only for trees are also established.