Premium
Fault‐tolerant minimum broadcast networks
Author(s) -
Ahlswede R.,
Gargano L.,
Haroutunian H. S.,
Khachatrian L. H.
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199607)27:4<293::aid-net4>3.0.co;2-b
Subject(s) - broadcasting (networking) , fault tolerance , computer science , broadcast communication network , parallel computing , task (project management) , telecommunications network , computer network , distributed computing , combinatorics , mathematics , engineering , systems engineering
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 n ( k ). In this paper, we study B k ( n ), the minimum number of communication lines of any minimal k ‐fault‐tolerant broadcast network on n processors. We give the value of B k ( n ) for several values of n and k and, in case k < [log n ], give almost‐minimum k ‐fault‐tolerant broadcast networks. © 1996 John Wiley & Sons, Inc.