----------------------- REVIEW 1 ---------------------
PAPER: 43
TITLE: Iterative Approximate Consensus in the presence of Byzantine Link Failures
AUTHORS: Lewis Tseng and Nitin Vaidya
OVERALL EVALUATION: 2 (accept)
REVIEWER'S CONFIDENCE: 3 (medium)
----------- REVIEW -----------
There has recently been a revival in interest in the problem of approximate
agreement in Byzantine systems. This paper looks at a new twist, where the
nodes are correct and synchronous, but the links may have transient Byzantine
faults.
The problem is the following: each process stars out with a real value, and the
processes must converge to values within \epsilon of one another, but also
within the range (beteen min and max) of the origingal inputs.
The paper derives necessary and sufficient graph conditions for algorithms of a
particular simple form (I-ABC) to exists. It was not clear to me whether there
could exist non-IABC algorithms for networks that fail the conditions given.
The presentation is clear. The model is unusual, but not contrived.
----------------------- REVIEW 2 ---------------------
PAPER: 43
TITLE: Iterative Approximate Consensus in the presence of Byzantine Link Failures
AUTHORS: Lewis Tseng and Nitin Vaidya
OVERALL EVALUATION: 1 (weak accept)
REVIEWER'S CONFIDENCE: 4 (high)
----------- REVIEW -----------
A few remarks.
This apper has "a lot of cut&paste" from the podc 2a12 ppaer by the same authors.
Here Byz processes arer replaced by Byz links.
Terminology is sometimes confusing:
In nearly all papers, due to its agreemnt property, "consensus" means "exact agreement".
Hence "approximate consensus" should be replaced by "approximate agreeement".
page 5, line - 4: "to exist" (no "to exists"
page 9, equation (2): T-i is defined with two parameters page 5 (equation (1));
and used with only one parameter in equation (2) page 9
page 9 (line -5) : it is written "Note that i \in N_i^*[t]$ an
page 10 line 2, it isd witten "i \notin N_i^*[t]$
there is some contradiction or only a typo???
Is the item 3 of algorithm 1 still correct?
This paper addsa nother member to the Zoo investigated by the authors
(see their refs 21-24).
----------------------- REVIEW 3 ---------------------
PAPER: 43
TITLE: Iterative Approximate Consensus in the presence of Byzantine Link Failures
AUTHORS: Lewis Tseng and Nitin Vaidya
OVERALL EVALUATION: 1 (weak accept)
REVIEWER'S CONFIDENCE: 3 (medium)
----------- REVIEW -----------
This paper presents an iterative algorithm, called Iterative Approximate Byzantine Consensun (IABC), to address the problem of reaching approximate consensus in presence of transient Byzantine link failures in a synchronous system.
Any iteration is divided in three steps: First, any node sends its state value along any outgoing link; Second, values are received and stored in a vector; Third a transition function takes the vector and the previous internal state to compute the new value. New state is assured to be in a convex hull of the states of all nodes at the end of the previous iteration. The number of iterations depend on the graph topology, on the upper and lower bounds among the initial state values and the approximation factor \epsilon.
Moreover they prove a tight neccessary and sufficient condition on the graph for the existence of the IABC for which the 2f+1 node and edge connectivity is not necessary.
On the positive side this is the first paper to address the approximate consensus problem in a transient Byzantine link failures system, introducing tight conditions of solvability.
On the weak side this work leverage heavily on ideas that are behind authors' previous works [21][23][24], as they themselves said. On my point of view would be interesting a more organic presentation of these metodologies to show how to solve different problems.
Other comments:
Usually abstract should not presents neither related works nor references.
typo: pag 4, "The iterative algorithm may terminate after a number of iterations that is a function of (I suppose \mu) and U."
----------------------- REVIEW 4 ---------------------
PAPER: 43
TITLE: Iterative Approximate Consensus in the presence of Byzantine Link Failures
AUTHORS: Lewis Tseng and Nitin Vaidya
OVERALL EVALUATION: 2 (accept)
REVIEWER'S CONFIDENCE: 4 (high)
----------- REVIEW -----------
This paper gives necessary and sufficient conditions for the solution to the iterative approximation problem in the presence of transient byzantine link failures on directed sparely connected communication graphs. This appears to be an extension of their previous work that gave necessary and sufficient conditions for the different but related problem of approximate consensus with byzantine node failures on a sparsely connected communication graph. Their main contribution is to give the tight necessary and sufficient conditions which they claim previous works have not done.
The paper seems to be well-written and I recommend accepting the paper. I have following suggestions:
1. Authors should motivate the problem by giving examples of situations where their algorithm can be used.
2. Authors should motivate the assumption that each process keeps restricted memory (just its state).
----------------------- REVIEW 5 ---------------------
PAPER: 43
TITLE: Iterative Approximate Consensus in the presence of Byzantine Link Failures
AUTHORS: Lewis Tseng and Nitin Vaidya
OVERALL EVALUATION: 2 (accept)
REVIEWER'S CONFIDENCE: 3 (medium)
----------- REVIEW -----------
The paper studies the problem of iterative consensus in the presence of transient Byzantine link failures. It identifies sufficient and necessary conditions for a network to reach consensus. The paper contains valuable contribution to the field of fault-tolerant computing.