Time bounds on fault‐tolerant broadcasting
Authors:
Abstract
Broadcasting is the process by which a message originated at one vertex is delivered to all other vertices of a network, subject to the restriction that a vertex may participate in only one message transfer during a given time unit. A k fault‐tolerant broadcasting scheme is a calling scheme that gurantees the completion of the broadcast in the presence of up to k link failures. Let Tk(n) denote the minimum time required for k fault‐tolerant broadcasting in an n‐vertex network. Liestman [Networks 15 (1985) 159–171] showed that for every n and k such that n − 2 ≥ k ≥ 1, Tk(n) ⩾ [log n]+k. This paper establishes a matching upper bound, showing that for such n and k, Tk(n) ϵ O (log n +k). In particular, we present various efficient broadcasting schemes achieving almost optimal multiplicative constants. Our best upper bound uses new partial results on a tree‐packing problem that may be of independent interest.Keywords
This publication has 12 references indexed in Scilit:
- Broadcasting in one dimensionDiscrete Applied Mathematics, 1988
- Generalizations of broadcasting and gossipingNetworks, 1988
- Fault-tolerant broadcast graphsNetworks, 1985
- Heuristic Algorithms for Broadcasting in Point-to-Point Computer NetworksIEEE Transactions on Computers, 1984
- Broadcasting in Trees with Multiple OriginatorsSIAM Journal on Algebraic Discrete Methods, 1981
- Information Dissemination in TreesSIAM Journal on Computing, 1981
- Minimum Broadcast TreesIEEE Transactions on Computers, 1981
- Minimum‐time line broadcast networksNetworks, 1980
- Minimal broadcast networksNetworks, 1979
- Minimum broadcast graphsDiscrete Mathematics, 1979