L. Gasieniec, A. Pelc, Broadcasting with a bounded fraction of faulty nodes,
*Journal of Parallel and Distributed Computing* 42 (1997), 11-20.

Abstract:

We consider the problem of broadcasting a message from one processor
(called the source) to *n* other processors.
We adopt the 1-port half-duplex model
in which every processor (node) can communicate with at most one
other node in a unit
of time and during this period one of the communicating nodes can only send
information and the other can only receive it. The source is fault-free but all
other nodes are subject to permanent failures. A faulty node can
receive the message but cannot relay it. The fraction of faulty
nodes is bounded by a constant. We consider non-adaptive broadcasting
algorithms working correctly in the presence of faulty nodes
and investigate their worst-case running time. We also show lower
bounds for broadcasting time under this scenario. Our main result is the
construction of a fault-tolerant broadcasting algorithm
whose running time is less
than 1.73 times larger than optimal, for sufficiently large *n*.

E.Kranakis, D.Krizanc, A. Pelc, Hop-congestion tradeoffs for
high speed networks,
*International Journal of Foundations of Computer Science* 8 (1997), 117-126.

A preliminary version appeared in: Proc. Seventh IEEE Symposium on Parallel and Distributed Processing, San Antonio, Texas, October 1995, pp. 662-668.

Abstract:

Message transmission in ATM networks is via virtual paths. Packets are routed along virtual paths by maintaining a routing field whose subfields determine the intermediary destinations of the packet. In such a network it is important to construct path layouts that minimize the hop number (i.e. the number of virtual paths used to travel between any two nodes) as a function of edge-congestion (i.e. the number of virtual paths passing through a link). In this paper we construct asymptotically optimal virtual path layouts for chains and meshes.

P. Berman, K. Diks, A. Pelc, Reliable broadcasting in logarithmic
time with Byzantine link failures,
*Journal of Algorithms* 22 (1997), 199-211.

Abstract:

Broadcasting is a process of transmitting a message held in one node of
a communication network to all other nodes. Links of the network are subject
to randomly and independently distributed faults with probability
* 0 < q < 1/2 *; faults are permanent and Byzantine, while all nodes are fault free. In a unit of time, each node can communicate with at most
one other node. We present a broadcasting algorithm which works for *n*
nodes in time *O(log n)* with probability of correctness exceeding
*1 - 1/n*, for sufficiently large *n*.

B. Chlebus, K. Diks, A. Pelc, Transition-optimal token distribution,
*Fundamenta Informaticae* 32 (1997), 313-328.

Abstract:

There is given a graph, that models a communication network of a multiprocessor
system, and there are tokens (jobs) allocated to nodes of the graph.
The task is to distribute the tokens evenly, subject to the constraint
that they may be moved only along the edges of the graph.
The cost of a distribution strategy is measured as the total number of
operations of moving a token along an edge.
An algorithm for general graphs is developed, by reduction to a maximum-flow
minimum-cost problem, that finds a cost-optimal distribution strategy, given
a graph and an initial token allocation.
The main result is an algorithm for graphs that are lines of nodes;
it finds the distribution strategy in time *O(n)*, for a line of *n* nodes.

K. Diks, A. Pelc, Globally optimal diagnosis in systems with random faults,
*IEEE Transactions on Computers* 46 (1997), 200-204.

Abstract:

We consider the problem of fault diagnosis in multiprocessor systems, under
a probabilistic model previously studied by Scheinerman and Blough,
Sullivan and Masson. Processors can test one another; fault-free
processors 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.
A diagnosis algorithm is *globally optimal* if it has
the highest probability
of correctness among all (deterministic) diagnosis algorithms. We give fast
globally optimal diagnosis algorithms for a class of test assignments
including complete directed graphs and
directed acyclic graphs. This is for
the first time that globally optimal diagnosis is given in a probabilistic
model without any assumptions on the behavior of faulty processors.