Comments from the editors and reviewers:

Reviewers' comments:


Reviewer #1: The authors consider the problem of broadcasting with locally bounded Byzantine faults in a 
network. The broadcast must work correctly whenever the neighborhood of any node contains at most t Byzantine faults. 
The main result of the paper is a necessary and sufficient condition
on the topology of the network for the Certified Propagation Algorithm to work correctly.
This result is correct and mildly interesting. Its drawback is that the condition is quite hard
(probably exponential) to verify, hence its utility is quite restricted. 
Moreover, the authors claim that their result solves an open problem from [7]. 
This is not the case. The open problems from [7] are stated as follows:

We pose two questions left for future
research. First, it may be interesting to close the
gap between our upper and lower bounds on t, perhaps
by introducing other, tighter parameters. Ideally, there
may be a single graph-theoretic parameter \phi(G) capturing
the threshold precisely (i.e., such that there is a
broadcast algorithm under the t-locally bounded scenario
if and only if t < \phiG) . Second, it is not clear
if the CPA algorithm is "unique" on ad-hoc networks,
in the sense that for any t-local fault configuration, if
some other rule works then so does CPA. 

The authors probably refer to the first of the above problems, but saying that they solve it is a misrepresentation. 
The complicated necessary and sufficient condition on the topology that they give has nothing to do with finding a tight parameter mentioned in the problem.

In spite of this, the paper can be published, provided that the following two changes are made:

1. The claim that the paper solves an open problem from [7] is withdrawn.
2. The complexity of verifying the condition is discussed: either the authors show that the condition
can be efficiently verified for any network, or they admit that its verification is (probably) exponential.