Premium
Fault‐tolerant broadcast graphs
Author(s) -
Liestman Arthur L.
Publication year - 1985
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/net.3230150203
Subject(s) - computer science , broadcasting (networking) , redundancy (engineering) , computer network , fault tolerance , graph , scheme (mathematics) , broadcast communication network , distributed computing , radio networks , theoretical computer science , mathematics , telecommunications , wireless network , wireless , mathematical analysis , operating system
Abstract Broadcasting refers to the process of information dissemination in a communications network whereby a message, originated by one member, is transmitted to all members of the network. By incorporating redundancy in the calling scheme, the completion of the broadcast may be guaranteed in the presence of up to k link failures. A k fault‐tolerant broadcast graph represents a network configuration which admits such a scheme. This article investigates these graphs and the tradeoff between the time allowed for broadcasting and the number of edges required in the graph.