✦ LIBER ✦

Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures

✍ Scribed by Piotr Berman; Krzysztof Diks; Andrzej Pelc

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 154 KB
Volume: 22
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0810

No coin nor oath required. For personal study only.

✦ Synopsis

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 unit of time, each node can communicate with at most one other node. We present a broadcasting Ž . algorithm which works for n nodes in time O log n with probability of correctness exceeding 1 y 1rn, for sufficiently large n.

📜 SIMILAR VOLUMES

Reliable communication in networks with

Reliable communication in networks with Byzantine link failures

✍ Andrzej Pelc 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 925 KB

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