Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Peleg et al. (1989) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: