Paper 2014/290

Reliable Broadcast with Respect to Topology Knowledge

Aris Pagourtzis, Giorgos Panagiotakos, and Dimitris Sakavalas


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 (2004) and the general adversary model of Hirt and Maurer (1997) and explore the tradeoff between the level of topology knowledge and the solvability of the problem. We refine the local pair-cut technique of Pelc and Peleg (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, that is, it can tolerate as many local corruptions as any other non-faulty algorithm; this settles an open question posed by Pelc and Peleg. We also provide an adaptation of CPA against general adversaries and show its uniqueness in this case too. To the best of our knowledge this is the first optimal algorithm for Reliable Broadcast in generic topology ad hoc networks against general adversaries.

Available format(s)
Publication info
Preprint. MINOR revision.
cryptographic protocolsdistributed cryptographyad hoc networkssecure broadcastbyzantine generalsreliable broadcastlocally bounded adversary modelgeneral adversary
Contact author(s)
sakaval @ corelab ntua gr
2014-05-19: revised
2014-04-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aris Pagourtzis and Giorgos Panagiotakos and Dimitris Sakavalas},
      title = {Reliable Broadcast with Respect to Topology Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2014/290},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.