----------------------- REVIEW 1 ---------------------
PAPER: 68
TITLE: Byzantine Vector Consensus in Complete Graphs
AUTHORS: Nitin Vaidya and Vijay Garg
----------- REVIEW -----------
This paper proves bounds for Byzantine vector consensus in complete graphs for both synchronous and asynchronous systems. In the vector consensus problem, processes start with a d-dimensional vector and they agree upon a d-dimensional vector that is in the convex hull of vectors of non-faulty processes. For synchronous systems, it shows that n >= max(3f + 1, (d+1) f + 1) is necessary and sufficient for exact BVC. For asynchronous systems, it shows that n>= (d+2) f + 1 is necessary and sufficient for approximate BVC. Exact BVC is impossible in asynchronous systems when processes can crash.
This work is to my knowledge novel and solid. The results are quite negative, though. They imply that the degree of replication grows linearly with the dimension of the input vectors.
As it points out, another problem has been called vector consensus in the literature, which is confusing. Perhaps a different, such as convex-hull consensus might avoid the confusion.
----------------------- REVIEW 2 ---------------------
PAPER: 68
TITLE: Byzantine Vector Consensus in Complete Graphs
AUTHORS: Nitin Vaidya and Vijay Garg
----------- REVIEW -----------
The paper considers Byzantine vector consensus (BVC), where non-faulty processes must agree on the same vector of points of dimension $d$, such that this vector must lie within the convex hull of the sets of points proposed by non-faulty processes. The exact version of this problem demands non-faulty processes to agree on exactly the same vector, whereas the approximate agreement requires only that the values of each coordinate of the decided vectors of any two non-faulty processes must be within $\epsilon$ of each other, for some $\epsilon > 0$. In particular, the paper provides two main contributions. The paper first shows that $n \geq \max(3f+1,(d+1)f+1)$ is necessary and sufficient for solving exact BVC in a synchronous environment, where $n$ and $f$ are the number of processes and the maximum number of Byzantine processes, respectively. The authors then prove that $n \geq (d+2)f + 1$ is necessary and sufficient for solving the approximate BVC.
On the positive side the paper provides necessary and sufficient conditions for both synchronous and asynchronous environments. On the negative side the added value is somewhat limited to the application of existing techniques and algorithms for deriving the necessary and sufficient conditions.
Regarding the synchronous case, the condition $n \geq 3f+1$ is well known from previous literature. The difficulty of this new problem for a synchronous system lies only in determining whether this is sufficient to fulfill the validity property, as defined in the paper. The authors show that one way to solve the problem is by simply having each correct process broadcasting its vector, such that all correct processes agree on $n$ input vectors. Each process then has to compute the intersection of the convex hull of each multiset of $n-f$ vectors. Using a simulation method, it is easily shown that if $n \leq (d+1)f$, then there may be no consensus. The Tverberg's theorem directly implies that for $n \geq (d+1)f +1$, all correct processes find a common set of Tverberg's points and deterministically decide the same vector.
The authors also propose the use of linear programming as a technique for computing the Tverberg's points as efficient as possible. However, the model of linear programming is never expressed in the standard form. The authors simply identify a set of linear restrictions of the problem and state that it is only necessary to find a vector $z$ that fulfills all these restrictions. Some detail is missing, such as, what would be the objective function. In its current form, this section is confusing. While I value the concern regarding the
complexity of the proposed solution (which may still be very complex even when using the best linear programming algorithms), I think this section could either be completely removed or significantly simplified if a more precise model were provided.
The result for the asynchronous approximate vector consensus significantly improve the value of the paper. Here, the authors reuse the simulation method to show that $n \geq (d+2)f +1$ is a necessary condition. To prove sufficiency, the approach proposed previously by Abraham et al. is simply adapted to the problem of Byzantine vector consensus. The original protocol works in asynchronous rounds, where in each round processes gather the proposals of at least other $n-f$ processes, such that any two correct processes see some
common set of $n-f$ values. A selection process ensures that the range of the values being proposed in each round is at most half the range of the previous round. Thus, a finite number of rounds is required to reach approximate agreement. The main difference for this paper is that the selection procedure is now to deterministically select some of the Tverberg's points as in the synchronous case. The authors also adapt the factor by which the range of values is decreased in each round.
In summary, the improvements over previous work are the application of the Tverberg's theorem to derive a method for finding valid solutions to the problem and for showing that these solutions exist exactly when the specified conditions hold; the adaptation of the algorithm proposed by Abraham et al. for Byzantine vector consistency.
----------------------- REVIEW 3 ---------------------
PAPER: 68
TITLE: Byzantine Vector Consensus in Complete Graphs
AUTHORS: Nitin Vaidya and Vijay Garg
----------- REVIEW -----------
Each process is given a d-dimensional input vector. Up to f processes may be Byzantine. In the exact version of the vector consensus problem, correct processes must agree on a vector in the convex hull of the input vectors. In the approximate version, the agreement property is relaxed to allow output vectors to be within distance epsilon of one another. This paper gives precise bounds on the number of Byzantine failures that can be tolerated when solving the exact problem synchronously and the approximate problem asynchronously.
The paper uses elegant geometric arguments to get nice results on a natural generalization of a classical problem.
The amount of local computation used by the synchronous algorithm in Section 2.2 is exponential in f, so there is some room for improvement in the future.
It might have been nice to give a slightly more concrete example of where the vector consensus problem would be useful, as motivation for the paper.
Minor comments:
p.6: Why does X_i^j have the subscript i? The definition does not seem to depend on i at all.
2nd line after equation (6): Why 4*epsilon? It seems bigger than necessary.
Sec 3.2, line 2: It might be unclear at this point what is meant by "asynchronous rounds".
p.7, line 11: "description" -> ", described"