2014 | OriginalPaper | Chapter
Reliable Broadcast with Respect to Topology Knowledge
Authors : Aris Pagourtzis, Giorgos Panagiotakos, Dimitris Sakavalas
Published in: Distributed Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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. To the best of our knowledge this is the first optimal algorithm for Reliable Broadcast in generic topology
ad hoc
networks against general adversaries.