Andrzej Pelc

We consider the problem of disseminating messages in networks. We are interested in information dissemination algorithms in which machines operate independently without any knowledge of the network topology or size. Three communication tasks of increasing difficulty are studied. In blind broadcasting (BB), the goal is to communicate the source message to all nodes. In acknowledged blind broadcasting (ABB), the goal is to achieve BB and inform the source about it. Finally, in full synchronization (FS), all nodes must simultaneously enter the state terminated after receiving the source message. The algorithms should be efficient both in terms of the time required and the communication overhead they put on the network. We limit the latter by allowing every node to send a message to at most one neighbor in each round. We show that BB is achieved in time at most 2n in any n‐node network and show networks in which time 2n − o(n) is needed. For ABB, we show algorithms working in time (2 + ϵ)n, for any fixed positive constant ϵ and sufficiently large n. Thus, for both BB and ABB, our algorithms are close to optimal. Finally, we show a simple algorithm for FS working in time 3n and a more complicated algorithm which works in time 2.9n. The optimal time of full synchronization remains an open problem. © 2001 John Wiley & Sons, Inc.

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.