✦ LIBER ✦

Fault-tolerant minimum broadcast networks

✍ Scribed by Ahlswede, R.; Gargano, L.; Haroutunian, H. S.; Khachatrian, L. H.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 978 KB
Volume: 27
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199607)27:4<293::aid-net4>3.0.co;2-b

No coin nor oath required. For personal study only.

✦ Synopsis

Broadcasting is the task of transmitting a message originated at one processor of a communication network to all other processors in the network. A minimal k-fault-tolerant broadcast network is a communication network on n vertices in which any processor can broadcast in spite of up to k line failures in optimal time T,,(k). In this paper, we study & ( n ) , the minimum number of communication lines of any minimal k-fault-tolerant broadcast network on n processors. We give the value of & ( n ) for several values of n and k and, in case k < Llog n j , give almost-minimum k-fault-tolerant broadcast networks. 0 1996 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Fault-Tolerant Broadcasting in Radio Net

Fault-Tolerant Broadcasting in Radio Networks

✍ Evangelos Kranakis; Danny Krizanc; Andrzej Pelc 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 151 KB

We consider broadcasting in radio networks that are subject to permanent node failures of unknown location. Nodes are spread in a region in some regular way. We consider two cases: nodes are either situated at integer points of a line or they are situated in the plane, at grid points of a square or

Fault-tolerant routings with minimum opt

Fault-tolerant routings with minimum optical index

✍ Jeffrey H. Dinitz; Alan Ling; Douglas R. Stinson 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

Designing optimal fault-tolerant star ne

Designing optimal fault-tolerant star networks

✍ Abdel Aziz Farrag; Robert J. Dawson 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 466 KB

Minimal selectors and fault tolerant net

Minimal selectors and fault tolerant networks

✍ Omid Amini; Frédéric Giroire; Stéphane Pérennes; Florian Huc 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 271 KB

Perfect Two-Fault Tolerant Search with M

Perfect Two-Fault Tolerant Search with Minimum Adaptiveness

✍ Ferdinando Cicalese; Daniele Mundici 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 256 KB

Broadcasting in synchronous networks wit

Broadcasting in synchronous networks with dynamic faults

✍ Chlebus, B. S.; Diks, K.; Pelc, A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 876 KB

The problem of broadcasting in a network is to disseminate information from one node to all other nodes by transmitting it over communication links that connect nodes. We consider the time of broadcasting in the presence of at most k dynamic link failures. If a node knows source information, then in