----------------------- REVIEW 1 ---------------------
PAPER: 49
TITLE: Reaching Approximate Byzantine Consensus with Multi-hop Communication
AUTHORS: Lili Su and Nitin Vaidya
OVERALL EVALUATION: 2 (accept)
----------- REVIEW -----------
This paper considers the approximate Byzantine agreement under an
extended communication model, where each node equips the direct
communication capability to the nodes within l hops. The authors
presents the necessary and sufficient condition about the network
topology in which the problem is solvable. The problem setting
can be regarded a generalization of several different models,
that is, the standard model corresponds to the case of l = 1, and
the complete network topology corresponds to l = \infty. For
both cases, the presented condition matches the necessary and
sufficient conditions already known.
The paper is well-written, and seems to show nice results.
While the model considered in this paper is slightly unnatural,
it well captures the previous results as a generalized one.
The reviewer feels that a linear-algebraic treatment of the
proposed algorithm and model looks pretty good, which may help
us to develop much more elegant theory on this topic.
The reviewer slightly wonders how the technical methodology
in this paper overlaps the authors prior work [12][15]. Since
the novelty of the technical methodology is not explicitly
stated, the reviewer is slightly doubtful of the possibility
that the paper is just a incremental refinement of the previous
papers. The camera-ready should touch and clarify the technical
improvement of this paper.
----------------------- REVIEW 2 ---------------------
PAPER: 49
TITLE: Reaching Approximate Byzantine Consensus with Multi-hop Communication
AUTHORS: Lili Su and Nitin Vaidya
OVERALL EVALUATION: 2 (accept)
----------- REVIEW -----------
In this paper, the author consider the Approximate Consensus Problem in directed networks when there are byzantine nodes. Compared to previous works, the specificity of the model considered here is that at each step, each node can send messages on paths of length at most l. If a byzantine node belongs to this path, it can tamper with the message.
They give a necessary and sufficient condition the network has to satisfy in order to be able to solve the problem. This condition is of course related to the connectivity of the lth power of the graph, but it is a bit more involved since faulty nodes can tamper all messages they see. The proof that the condition is necessary is quite standard. To show that it is sufficient, they propose an averaging algorithm where at each step, each node discard the messages it received with the smallest values and with the highest values. The algorithm is rather simple but the proof of its correctness is rather involved.
At the end of the paper, they show that in the case where l is big enough so that all paths of the graph are shorter than l, then their condition coincide with existing results in the litterature.
I think the paper is interesting. I did not check all the proofs but what I read was rather convincing. The paper is well written and (except for the ibg technical proof) easy to read (even for a non-expert).
----------------------- REVIEW 3 ---------------------
PAPER: 49
TITLE: Reaching Approximate Byzantine Consensus with Multi-hop Communication
AUTHORS: Lili Su and Nitin Vaidya
OVERALL EVALUATION: 2 (accept)
----------- REVIEW -----------
The paper generalizes the consensus problem in distributed system with Byzantine faults to the case of arbitrary network topologies. The authors impose a limitation on path length in communication between nodes: within one iteration, a pair of nodes may only exchange messages along paths of length at most $l$. Given the number of faults $f$ which may appear, the main result of the paper is a structural condition on the network topology, which is necessary and sufficient to ensure a solution to Byzantine consensus. The condition is based on a minimum-cut-type criterion, and "interpolates" between two subcases of the problem which had been studied previously in the literature, those of $l=+\infty$ and $l=1$.
As a natural generalization of a fundamental problem of distributed computing, the paper deserves acceptance.
One minor concern to be addressed is the lack of a formal description of the capabilities of a Byzantine node. Some of the discussion in Section 6 suggests that the power of the Byzantine node is in fact significantly limited (at least compared to the usual unrestricted scenario on the complete network). Perhaps a comparison of the different models of faults between this paper and some of the cited references (e.g. [6,9,12,15]) would be in order.
The paper is generally well written. Some plural/singular forms of words need to be corrected in the introduction. On page 2, a reference to "Vaidya et al." might be missing one or more citations.