Abstracts of papers published in 1995

A. Pelc, Almost safe Byzantine Agreement in sparse networks with random faults, Parallel Processing Letters 5 (1995), pp. 489-497.


We consider the Byzantine Agreement problem assuming that nodes of a network fail independently with fixed probability 0 < p < 1. The goal is to construct almost-safe agreement protocols working for classes of sparse n-node networks. For such protocols, the probability of reaching consensus, under any behavior of faulty nodes, must converge to 1 as n grows. For p < 1/3 and every function L : N ---> N growing faster than linear, we show n-node networks with L(n) links and an almost-safe Byzantine Agreement protocol working for these networks. We also construct such a protocol working for a large class of n-node networks of maximum degree O(log n). We show, further, that these networks are asymptotically sparsest possible to support almost-safe Byzantine Agreement.

K. Diks, A. Malinowski, A. Pelc, Token transfer in a faulty network, RAIRO, Theoretical Informatics and Applications 29 (1995), pp.383-400.


A token originally situated in a given fault-free node of the complete network, called the source, has to visit all other fault-free nodes. Links and/or nodes of the network fail independently with probabilites p < 1 and q < 1, respectively. In a unit of time every node can be involved in at most one transmission; transmissions along a faulty link or involving a faulty node do not succeed. We consider various communication models depending on the ability of nodes to modify their behavior according to the outcome of previous transmissions. For all models we present token transfer algorithms working fast and with probability of correctness exceeding 1- n-e, where n is the number of nodes and e an arbitrary positive constant.

K. Diks, E. Kranakis, A. Malinowski, A.Pelc, Anonymous wireless rings, Theoretical Computer Science 145 (1995), pp. 95-109.

The results of this paper were announced in: K. Diks, E. Kranakis, A. Malinowski, A. Pelc, The buffer potential of a network, Proc. 1st Colloquium on Structural Information and Communication Complexity, SIROCCO'94, May 1994, Ottawa, Canada, pp. 149-150.


We introduce anonymous wireless rings: a new computational model for ring networks. In the well-known hardware ring each processor has two buffers, one corresponding to each of its neighbors. In the wireless ring each processor has a single buffer and cannot distinguish which neighbor the arriving bit comes from. This feature substantially increases anonymity of the ring. A priori it is not clear whether any non-trivial computation can be performed on wireless rings. Nevertheless we show that wireless rings are computationally equivalent to hardware rings.