----------------------- REVIEW 1 ---------------------
PAPER: 43
TITLE: Iterative Byzantine Vector Consensus in Incomplete Graphs
AUTHORS: Nitin Vaidya
OVERALL EVALUATION: 2 (accept)
REVIEWER'S CONFIDENCE: 4 (high)
Technical Correctness: 4 (good)
Novelty: 3 (fair)
Relevance: 3 (fair)
Presentation: 3 (fair)
Best Paper Candidate?: 1 (No)
----------- REVIEW -----------
In the Byzantine Vector Consensus (BVC) problem each process starts with a point in R^d
and each correct processes is required to decide a point in the convex hull defined by
the inputs of non-faulty processes. The decisions of every two correct processes must be a distance at most \epsilon, where \epsilon is a predefined parameter.
This problem has been recently study independently by Mendes and Herlihy, and Vaidya and Garg in (synchronous and asynchronous) message-passing systems prone to Byzantine failures where the underlying network of communication is a complete graph.
This paper extends the results of Mendes-Herlihy and Vaidya-Garg to the synchronous case in which the underlying communication network is not a complete graph. It presents a sufficient condition for solving BVC in such a system. It also presents a necessary condition for solving BVC, which does not match the sufficient condition.
I do not see why the author emphasizes so much that the paper considers round-based algorithms when, as far as I understand, the model is the same as in hundreds of papers. What is different is that the algorithms are memory-less in the sense that processes remember only an estimation at the beginning of every round.
Indeed, the assumption of being memory-less is good for the possibility result because it shows that these apparently weak algorithms can solve BVC. However, the assumption is bad for the impossibility result. It would be good if the same result can be proved to full-information algorithms. Or maybe that is the reason the necessary and the sufficient condition do not match.
Detailed comments:
-- In Condition NC, I do not see what is the relation with the dimension d. The condition is related with a property of the graph, which is part of the model, while the dimension d is part of the problem.
-- There are no symbols of QED.
-- Lemma 4. Should it be |F| \leq f ?
-- Alg. Byz-Iter, Termination section. Say ``Inequation (9)''. I was confused what is that (9) about.
-- End of Sec 5.2. There are two claims without a numbering.
----------------------- REVIEW 2 ---------------------
PAPER: 43
TITLE: Iterative Byzantine Vector Consensus in Incomplete Graphs
AUTHORS: Nitin Vaidya
OVERALL EVALUATION: 2 (accept)
REVIEWER'S CONFIDENCE: 3 (medium)
Technical Correctness: 4 (good)
Novelty: 4 (good)
Relevance: 5 (excellent)
Presentation: 5 (excellent)
Best Paper Candidate?: 2 (Maybe)
----------- REVIEW -----------
The paper studies the d-dimensional approximate consensus problem in the synchronous, byzantine, message passing model. This problem was studied recently for complete graphs in synchronous as well as asynchronous systems. In this paper, the problem is studied for the incomplete graphs.
A particular class of solutions, called "iterative algorithms" that maintain the state at the end of each round purely in the form of a vector within the convex hull of the proposals, is studied in the paper. A necessary condition (satisfied by any graph for which an iterative algorithm is possible) is stated. A sufficiency condition and an iterative algorithm that meets this condition are also proposed. The necessary and sufficient conditions match for d = 1, but not for higher values of d.
In my view the paper extends the work initiated by the author that has subsequently been pursued by others and published in the top venues. The results reported here are elegant and nontrivial. I recommend acceptance.
I have a question to the author: if one is wiling to consider non-iterative algorithms, would it be correct to simply do byzantine consensus and agree on some process' input vector as the decision value? (With this algorithm, however, the decision vector could turn out to be a faulty process' input vector, if the algorithm does not solve *uniform* byzantine consensus. Is that an issue? It would be good to discuss this in the Introduction.)
----------------------- REVIEW 3 ---------------------
PAPER: 43
TITLE: Iterative Byzantine Vector Consensus in Incomplete Graphs
AUTHORS: Nitin Vaidya
OVERALL EVALUATION: 1 (weak accept)
REVIEWER'S CONFIDENCE: 4 (high)
Technical Correctness: 4 (good)
Novelty: 3 (fair)
Relevance: 4 (good)
Presentation: 4 (good)
Best Paper Candidate?: 1 (No)
----------- REVIEW -----------
The paper is a follow up of two of the author¡¦s previous papers. In [14], he (together with Tseng and Liang) considered scalar (i.e., the usual 1 dimension) consensus in *incomplete* graphs in presence of Byzantine faults. In [13] he (together with Grag) has addressed Byzantine *vector* consensus in systems that can be modeled by a complete graph. In this paper, he looks at the missing part and considered Byzantine vector consensus in incomplete graphs. (He considers a restricted class of possible algorithms called iterative algorithms.) Necessary and sufficient conditions are provided for vector consensus. The necessary condition does not match with the sufficient condition. The results are technically interesting.
On page 1, you write ¡§The correctness conditions for Byzantine vector consensus (elaborated below) cannot be satisfied by independently performing consensus on each element of the input vectors;¡¨ Why? where you discuss and elaborate on this?