----------------------- REVIEW 1 ---------------------
PAPER: 29
TITLE: Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs
AUTHORS: Nitin Vaidya, Lewis Tseng and Guanfeng Liang
Given the hardness of consensus under Byzantine faults, a natural area of focus has been the study of
approximate consensus, in which the non-faulty nodes' states are points in some space, and where there
is a natural notion of convergence of these states over time. Tight conditions for the existence of
algorithms that achieve this has been studied before for special classes of graphs; this paper does
so for arbitrary given directed graphs (where a directed edge connotes the possibility of communication).
The algorithm and analysis are inspired by prior work. Overall, this is progress on a fundamental
problem.
Comments for the authors: The convergence rate of your algorithm is implicit in Lemma 1 which comes quite
late in the paper; also, the important parameter alpha is somewhat buried in (3). Make both more explicit.
The use of italicized and boldface words is somewhat excessive. Please reduce these.
----------------------- REVIEW 2 ---------------------
PAPER: 29
TITLE: Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs
AUTHORS: Nitin Vaidya, Lewis Tseng and Guanfeng Liang
In this paper, authors propose a necessary and sufficient condition to
solve the iterative approximate byzantine consensus in directed
graph. They assume the synchronous reliable model of communication
(however, they relax this hypothesis in the last section of the paper by
showing, using existing techniques, how to bring their solutions to
asynchronous systems). They proposed two versions their necessary
conditions, the second one being more intuitive. Then, they established
the correctness of their sufficient condition by proposing an
algorithm that is correct assuming this condition.
The paper is well organized and well written. The topic is interesting
and clearly in the scope of the conference. The presented results are
original, technically sound, and somehow nice.
minor comments:
Introduction "therefore, for acheving approximate
consensus", I agree for the sufficent condition, I don't think it is
right for the necessary one as you consider a weaker version of the
problem.
Page 3, related works: more explanation about the difference between
the paper tand [13] are required.
Page 4, second bullet, I think there is a copy/past error!
----------------------- REVIEW 3 ---------------------
PAPER: 29
TITLE: Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs
AUTHORS: Nitin Vaidya, Lewis Tseng and Guanfeng Liang
This paper gives a simple necessary and sufficient criteria in the topology of a network and an iterative process which brings nodes which start with various input values to an increasingly narrower ranges of values, in the presence of