K. Diks, A. Pelc, Almost safe gossiping in bounded degree networks,
SIAM Journal on Discrete Mathematics 5 (1992), pp. 338-344.
K. Diks, A. Pelc, Almost safe gossiping in bounded degree networks,
SIAM Journal on Discrete Mathematics 5 (1992), pp. 338-344.
Abstract:
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 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.
A. Pelc, Broadcasting time in sparse networks with faulty transmissions,
Parallel Processing Letters 2 (1992), pp. 355-361.
Abstract:
One node of a communication network holds a message which should reach all other nodes. In a unit of time a node can communicate with all neighbors but some transmissions may be faulty. In the model assuming a bounded number of failures per time unit, all nodes must get the message for any location of faults, while for random independent failures the goal is to reach all nodes with high probability, for large networks. We establish relations between the number of links in networks and the time of fault-tolerant broadcasting.
A. Pelc, Reliable communication in networks with Byzantine link failures,
Networks 22 (1992), pp. 441-459.
Abstract:
We consider the problem of communication between nodes of a network whose links are subject to arbitrary failures: A failed link may not only stop transmitting messages but may corrupt them in any possible way. We characterize networks allowing communication in spite of at most t failures. Also, for every fixed link failure probability p < 0.29 we construct a class of networks for which the probability of successful communication converges to 1 as the number of nodes grows. It is shown that the number of links in these networks is asymptotically smallest possible to assure reliable communication. Moreover, in these networks, communication can be completed in just two information exchange rounds. Finally, we give a protocol assuring reliable communication in the hypercube if link failure probability is p < 0.02 and show that no such protocol exists if p > 0.15.
D. Blough, A. Pelc, Complexity of fault diagnosis in comparison models,
IEEE Transactions on Computers 41 (1992), pp. 318-324.
Abstract:
In this paper, we consider a comparison-based probabilistic model for multiprocessor fault diagnosis. We study the problem of optimal diagnosis, which is to correctly identify the status (faulty/fault-free) of units in the system, with maximum probability. For some parameter values, this probabilistic model is well approximated by the asymmetric comparison model introduced by Malek. For arbitrary systems it is shown that optimal diagnosis in the probabilistic model and in Malek's model is NP-hard. However, we construct efficient diagnosis algorithms in the asymmetric comparison model for a class of systems corresponding to bipartite graphs which includes hypercubes, grids and forests. Furthermore, for ring systems, we present a linear-time algorithm to perform optimal diagnosis in the probabilistic model.
A. Pelc, Optimal fault diagnosis in comparison models,
IEEE Transactions on Computers 41 (1992), pp. 779-786.
Abstract:
In comparison models for system-level fault diagnosis pairs of units are given the same job and results are compared. The result of such a comparison test can be 0 (match) or 1 (mis-match) and diagnosis is based on the collection of test results. Two such models have been studied, among others: the symmetric model of Chwa and Hakimi and the asymmetric model of Malek. We give worst case optimal testing algorithms for t-fault detection, sequential t-fault diagnosis and one-step t-fault diagnosis in both models. We discuss non-adaptive and adaptive testing and show that the latter often enables to decrease the number of tests.