Reliable broadcast with respect to topology knowledge

We study the Reliable Broadcast problem in incomplete networks against a Byzantine adversary. We examine the problem under the locally bounded adversary model of Koo (Proceedings of the 23rd annual ACM symposium on principles of distributed computing, PODC ’04, St. John’s, Newfoundland, Canada, 25–28 July 2004, ACM New York pp 275–282, 2004) and the general adversary model of Hirt and Maurer (Proceedings of the 16th annual ACM symposium on principles of distributed computing, PODC ’97, Santa Barbara, California, USA, August 21–24, 1997 ACM, New York pp 25–34, 1997) and explore the tradeoff between the level of topology knowledge and the solvability of the problem. In order to explore this tradeoff we introduce the partial knowledge model which captures the situation where each player has arbitrary topology knowledge. We refine the local pair-cut technique of Pelc and Peleg (Inf Process Lett 93(3):109–115, 2005) in order to obtain impossibility results for every level of topology knowledge and any type of corruption distribution. On the positive side we devise protocols that match the obtained bounds, and thus, exactly characterize the classes of graphs in which Reliable Broadcast is possible. Among others, we show that Koo’s Certified Propagation Algorithm (CPA) is unique, against locally bounded adversaries in ad hoc networks, among all safe algorithms, i.e., algorithms which never cause a node to decide on an incorrect value. This means that CPA can tolerate as many local corruptions as any other safe algorithm; this settles an open question posed by Pelc and Peleg. We also provide an adaptation of CPA achieving reliable broadcast against general adversaries and prove that this algorithm too is unique under this model. To the best of our knowledge this is the first optimal algorithm for Reliable Broadcast in generic topology ad hoc networks against general adversaries.