Time bounds on fault‐tolerant broadcasting
David Peleg, Alejandro A. Schäffer · Networks · 1989
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 T k (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, T k (n) ⩾ [log n ]+ k . This paper establishes a matching upper bound, showing that for such n and k , T k (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.