We improve both the upper and the lower bound of that paper providing a randomized algorithm for constructing a k-shot broadcasting schedule of length D+O(kn1/2klog2+1/kn) on undirected graphs, and a lower bound of D+Ω(k⋅(n−D)1/2k), which almost closes the gap between these bounds. For the unknown topology model, we provide the first k-shot broadcasting algorithm.
Assuming that each node knows only the network size n (or a linear upper bound on it), our randomized k-shot broadcasting algorithm completes broadcasting in O((D+min{D⋅k,logn})⋅n1/(k−1)logn) rounds with high probability for k≥2, and in 14eeaa92d52bce075de24b2bb0671" title="Click to view the MathML source">O(D⋅n2logn) rounds with high probability for k=1. Moreover, we present an Θ(logn)-shot broadcasting algorithm that completes broadcasting in at most O(Dlogn+log2n) rounds with high probability. This algorithm matches the broadcasting time of the algorithm of Bar-Yehuda et al. (1992), which assumes no limitation on the maximum number of transmissions per node.