K. Diks, E. Kranakis, A. Pelc, Perfect broadcasting in unlabeled networks,
*Discrete Applied Mathematics* 87 (1998), 33-47.

Abstract:

We consider broadcasting a message from one node to all other nodes of an
asynchronous totally unlabeled network:
neither nodes nor links of the network have
*a priori* assigned labels
but all nodes know the topology of the network.
Nodes can send messages of arbitrary
size and we are interested in minimizing the total number of messages.
Broadcasting in an *n*-node unlabeled network is *perfect* if it uses
*n-1* messages (the minimum even in the labeled network).
We show that the problem of deciding whether an arbitrary network
admits perfect broadcasting
from a given source, is NP-hard.
We characterize regular networks in which perfect
broadcasting from every node is possible, and give such broadcasting algorithms.

A. Pelc, Optimal diagnosis of heterogeneous systems with random faults,
*IEEE Transactions on Computers* 47 (1998), 298-304.

Abstract:

We consider the problem of fault diagnosis in multiprocessor systems.
Processors perform tests on one another; fault-free
testers correctly identify the fault status of tested processors, while
faulty testers can give arbitrary test results. Processors fail
with arbitrary probabilities and all failures are independent.
The goal is to identify
correctly the status of all processors, based on the set of test results.
A diagnosis algorithm is *optimal* if it has
the highest probability
of correctness (*reliability*) among all
(deterministic) diagnosis algorithms.
We give a fast diagnosis algorithm and prove its optimality for arbitrary
values of failure probabilities. This is for the first time that
optimal diagnosis is given for systems without any assumptions
on the behavior of faulty processors or on the values of failure probabilities.

We also investigate *locally optimal* diagnosis algorithms:
for any set of test results they return the most probable
configuration of faulty
and fault-free processors that could yield it.
We show a fast diagnosis which is always locally optimal.
If all processors have
failure probabilities smaller than 1/2, a locally optimal diagnosis
is proved to be optimal. However, if
some processors have failure probabilities exceeding 1/2, a locally
optimal diagnosis need not have the highest reliability. We even
show examples that it may have
arbitrarily small reliability, when the number of processors increases, while
optimal reliability remains constant.

A. Pelc, E. Upfal, Reliable fault diagnosis with few tests,
*Combinatorics, Probability & Computing* 7 (1998), 323-333.

Abstract:

We consider the problem of fault diagnosis in multiprocessor systems.
Processors perform tests on one another; fault-free
testers correctly identify the fault status of tested processors, while
faulty testers can give arbitrary test results. Processors fail
independently with constant probability *p<1/2* and the goal is to identify
correctly the status of all processors, based on the set of test results.
For *0 < q < 1*, *q*-diagnosis is a fault diagnosis algorithm whose probability of
error does not exceed *q*. We show that the minimum number of tests to perform
*q*-diagnosis for *n* processors is of order
* Theta(n log (1/q))* in the nonadaptive case and of order
*n +Theta(log (1/q))* in the adaptive case.
We also investigate *q*-diagnosis algorithms that minimize the maximum
number of tests performed by, and performed on, processors in the system,
constructing testing schemes in which each processor is involved in very
few tests.
Our results demonstrate that the flexibility yielded by
adaptive testing permits a significant saving in the number of tests for the
same reliability of diagnosis.

A. Czumaj, L. Gasieniec, A. Pelc, Time and cost trade-offs in gossiping,
* SIAM Journal on Discrete Mathematics* 11 (1998), 400-413.

Abstract:

Each of *n* processors has a value which
should be transmitted to all other processors.
This fundamental communication task is called *gossiping*.
In a unit of time every processor can communicate
with at most one other processor and during such a transmission
each member of a communicating pair learns all values currently known to the
other.
Two important criteria of efficiency of a gossiping algorithm are
its running time and the total number of transmissions.
Another measure of quality of a gossiping algorithm is the total number of links
used for transmissions. This is the minimum cost of
a network which can support the gossiping algorithm.
We establish trade-offs between the time *T* of gossiping and the number *C*
of transmissions and between the time of gossiping and the number *L*
of links used by the algorithm.
For a given *T* we construct gossiping algorithms working in time *T*, with
parameters *C* and *L* close to optimal.

K. Diks, A. Pelc, System diagnosis with smallest risk of error,
*Theoretical Computer Science* 203 (1998), 163-173.

Preliminary version appeared in: Proc. 22nd International Workshop on Graph Theoretic Concepts in Computer Science WG'96, Cadenabbia, Italy, June 1996, LNCS 1197, p. 141-150.

Abstract:

We consider the problem of fault diagnosis in multiprocessor systems.
Every processor can test its neighbors; fault-free
processors correctly identify the fault status of tested neighbors, while
faulty testers can give arbitrary test results. Processors fail
independently with constant probability *p<1/2* and the goal is to identify
correctly the status of all processors, based on the set of test results.
We give fast diagnosis algorithms with
the highest possible probability
of correctness for systems represented by complete bipartite graphs and by
simple paths.
This is for the first time that the most reliable fault diagnosis is given
for these systems in a probabilistic
model without any assumptions on the behavior of faulty processors.

E. Kranakis, D. Krizanc, A. Pelc, D.Peleg,
Approximate maxima finding of continuous functions under restricted budget,
*Theoretical Computer Science* 203 (1998), 151-162.

A preliminary version appeared in: Proc. 22nd International Workshop on Graph-Theoretic Concepts in Computer Science WG '96, Cadenabbia, Italy, June 1996, LNCS 1197, p. 268-278.

and the results were announced in: E. Kranakis, D. Krizanc, A. Pelc, D. Peleg, The complexity of data mining on the Web, Proc. 15th ACM Symp. on Principles of Distributed Computing PODC'96, Philadelphia, Pennsylvania, USA, (short abstract), p. 153.

Abstract:

A function is distributed among nodes of a graph in a ``continuous''
(or ``slowly changing'') way,
i.e., such that the difference between values stored at adjacent nodes
is small. The goal is to find a node of maximum value by probing some
nodes under a restricted budget. Every node has an associated cost
which has to be paid for probing it and a probe reveals the value of
the node. If the total budget is too small to allow probing every
node, it is impossible to find the maximum value in the worst case.
Hence we seek an *Approximate Maxima Finding (AMF)* algorithm that offers
the best worst-case guarantee *g*, i.e., for any continuous
distribution of values it finds a node whose value differs from the
maximum value by at most *g*.

Approximate Maxima Finding in graphs is related to a generalization of the multicenter problem and we get new results for this problem as well. For example, we give a polynomial algorithm to find a minimum cost solution for the multicenter problem on a tree, with arbitrary node costs.

K. Diks, E. Kranakis, A. Pelc, Broadcasting in unlabeled tori,
*Parallel Processing Letters* 8 (1998), 177-188.

Abstract:

We consider broadcasting a message from one node to all other nodes of an
asynchronous totally unlabeled torus:
neither nodes nor links have *a priori* assigned labels
but they know the topology and the size of the torus.
Nodes can send messages of arbitrary
size and we are interested in minimizing the total number of messages.
A naive broadcasting algorithm in a *n* x *n* totally unlabeled torus uses
*3n ^{2} +1* messages, while the obvious lower bound is

K. Diks, S. Dobrev, E. Kranakis, A. Pelc and P. Ruzicka,
Broadcasting in unlabeled hypercubes with linear number of messages,
*Information Processing Letters* 66 (1998), 181-186.

Abstract:

We consider broadcasting a message from one node to all other nodes of an
asynchronous totally unlabeled *n*-node hypercube.
Neither nodes nor links have * a priori* assigned labels.
We show a broadcasting algorithm which uses only *O(n)* messages. This answers affirmatively an open question of G. Tel.

A.Farley, A. Pelc, A.Proskurowski, Minimum-time multidrop broadcast,
*Discrete Applied Mathematics* 82 (1998), 59-75.

Abstract:

The multidrop communication model assumes that a message originated by a sender is sent along a path in a network and is communicated to each site along that path. In the presence of several concurrent senders, we require that the transmission paths be vertex-disjoint. The time analysis of such communication includes both start-up time and drop-off time terms. We determine the minimum time required to broadcast a message under this communication model in several classes of graphs.

L. Gasieniec, A. Pelc, Broadcasting with linearly
bounded transmission faults,
*Discrete Applied Mathematics* 83 (1998), 121-133.

Abstract:

We consider broadcasting with a linearly bounded number of transmission
failures. For a constant parameter
* a < 1 * we assume that at most *ai* faulty transmissions can occur during
the first *i* time units of the communication process, for every natural
number *i*. Every informed node can transmit information to at most
one neighbor in a unit of time. Faulty transmissions have no effect.
We investigate worst-case optimal non-adaptive
broadcasting time under this fault model,
for several communication networks. We show, for example, that for
the *n*-node line network
this time is linear in *n*, if * a < 1/2*, and exponential otherwise.
For the hypercube and the complete graph, broadcasting in the linearly
bounded fault model can be performed in time logarithmic in the number of
nodes.