Abstracts of papers published in 1997


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.