Communication-efficient broadcasting in complete networks with dynamic faults (Q1762999)

We consider the problem of message (and bit) efficient broadcasting in complete networks with dynamic faults. Despite the simplicity of the setting, the problem turned out to be surprisingly interesting from the algorithmic point of view. In this paper we show an \(\Omega(n+t f^{t/(t-1)})\) lower bound on the number of messages sent by any \(t\)-step broadcasting algorithm, where \(f\) is the number of faults per step. The core of the paper contains a constructive \(O(n+tf^{(t+1)/t})\) upper bound. The algorithms involved are of time complexity \(O(t)\), not strictly \(t\). In addition, we present a bit-efficient algorithm of \(O(n\log^2 n)\) bit and \(O(\log n)\) time complexities. We also show that it is possible to achieve the same message complexity even if the nodes do not know the \(id\)'s of their neighbours, but instead have only a weak sense of direction.