๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Reliable communication in networks with Byzantine link failures

โœ Scribed by Andrzej Pelc

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
925 KB
Volume
22
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 1 failures. Also, for every fixed link failure probability p 5 .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 5 .02 and show that no such protocol exists if p 2 .15.

๐Ÿ“œ SIMILAR VOLUMES

Reliable Broadcasting in Logarithmic Tim
Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures
โœ Piotr Berman; Krzysztof Diks; Andrzej Pelc ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 154 KB

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 1 randomly and independently distributed faults with probability 0q -; faults 2 are permanent and Byzantine, while all nodes are fault-free. In a un

Network reliability with node failures
Network reliability with node failures
โœ Liu, Shaobin; Cheng, Kam-Hoi; Liu, Xiaoping ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 101 KB

Given a graph whose edges never fail but whose nodes fail independently of each other with a constant probability 1 ---p p p, the reliability of a graph is defined to be the probability that the induced subgraph of the surviving nodes is connected. Let โ„ฆ (n n n, m m m) be the class of all graphs wit

Partition-based algorithm for estimating
Partition-based algorithm for estimating transportation network reliability with dependent link failures
โœ Agachai Sumalee; David P. Watling ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› Institute for Transportation Inc. ๐ŸŒ English โš– 133 KB

## Abstract Evaluating the reliability of a transportation network often involves an intensive simulation exercise to randomly generate and evaluate different possible network states. This paper proposes an algorithm to approximate the network reliability which minimizes the use of such simulation