We consider the problem of constructing reliable comparator networks built from unreliable comparators. In case of a faulty comparator inputs are directly output without comparison. A trivial lower bound of Ω(logn + k) on the depth of n-input k-fault tolerant sorting network is well known. We are interested in establishing exact lower bounds on the depth of such networks. To this end we consider fairly simple minimum-finding networks. 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 faulty comparators. We prove that the depth of any such network is at least max([logn] + 2k, logn + klog logn/k+1). We also describe a network whose depth nearly matches the lower bound.

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.

We consider probabilistic diagnosis in multiprocessor systems. Processors can test one another; fault-free processors give correct test results, while faulty testers are unpredictable. 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 the first time that globally optimal diagnosis is given in a probabilistic model without any assumptions on the behavior of faulty processors.

In broadcasting, information originally held in one node of a communication network (called the source) has to be transmitted to all other nodes. In a unit of time, every node which already received the source message can transmit it to one neighbor. in classical broadcasting, the choice of neighbors to be informed by a node and the order in which they are informed may depend on the source. Thus, nodes need to store many transmission lists corresponding to different possible sources and need to know the source to adapt their behavior accordingly. In this paper, we consider a variant of broadcasting in which every node is given a priori a single ordered list containing some of its neighbors. This list is meant to be universal for all possible sources. Upon obtaining the source message, a node transmits it to the neighbors from its list in prescribed order and then stops. This requires substantially less local memory devoted to schedule communication but usually increases broadcasting time. We compare broadcasting time in this and in the classical model and design optimal broadcasting schemes in the universal-list model for trees, rings, and grids. For tori and for complete graphs, we give upper bounds on broadcasting time. © 1996 John Wiley & Sons, Inc.

Every node of a communication network has a constant size value which should be made known to all other nodes. Nodes and links fail independently with constant probabilities $p < 1$ and $q < 1$, respectively. Faults are permanent and of crash type: a faulty link does not transmit messages and a faulty node neither sends nor receives messages. In a unit of time, every node can send a packet of information to at most one neighbor and receive a packet from at most one neighbor. The size of each packet does not exceed $b(n)$, where n is the number of nodes. For every $\eta > 0$ we present an algorithm to exchange values between all fault-free nodes of an n-node network in time $O(\frac{n}{b(n)}) + \log n$), with probability exceeding $1 - n^{ - \eta } $, for sufficiently large n. This order of magnitude of running time is optimal.

A mesh-connected processor array is considered in which the links are faulty in the following sense: Each attempt by two neighboring processors to communicate by exchanging messages may fail with some constant probability. A message sent across a link and not delivered is said to be delayed by the link. It is assumed that all the links delay with the same fixed delay probability, independently of each other. The problem of sorting is addressed in this model. It is proved that an $n \times n$ mesh can be sorted in the expected time $O( n )$ with large probability. More precisely, it is shown that there are two constants $c > 0$ and $r > 1$, depending on the delay probability, such that the $n \times n$ mesh is sorted in time $cn + t$ with the probability at least $1 - r^{ - t} $. One specific algorithm is considered, but the analysis shows that many known algorithms could sort in the expected time $O( n )$, after some natural modifications.

A variant of the well-known gossip problem is studied. Each of n members of a communication network has a piece of information that should be made known to everybody else. This is to be done by placing a sequence of two-party phone calls along the lines of the network. During each call, the two participants exchange all information they currently have, in a unit of time. It is assumed that calls fail independently with fixed probability $0 < p < 1$ and that no information is exchanged during a failed call. For communication networks of bounded degree, efficient schemes of calls are shown that assure complete communication with probability converging to 1 as n grows. Both the number of calls and the time they use are of minimal order.

We show that a 5-colouring of the vertices of an n-vertex planar graph may be computed in $O(\log n\log ^ * n)$ time by an exclusive-read exclusive-write parallel RAM with $O({n / {(\log n\log ^ * n)}})$ processors. Our algorithm, while faster than all previously known methods, is at the same time the first parallel 5-colouring algorithm to exhibit an optimal speedup. Optimality is achieved through a method based on the accelerating cascades technique and of independent interest. It should be emphasized that although input to the algorithm is a planar graph, we do not require a planar embedding to be given as part of the input. Other results concern the colouring of graphs of bounded genus and the construction of search structures for triangular planar subdivisions.