----------------------- REVIEW 1 ---------------------
PAPER: 46
TITLE: Relaxed Byzantine Vector Consensus
AUTHORS: Zhuolun Xiang and Nitin H. Vaidya
----------- Review -----------
This submission considers several ways Byzantine vector consensus can be relaxed to reduce the number of processes needed to reach agreement in high dimensions. While the original problem requires agreement within the convex hull of the valid inputs, the relaxed problem replaces the convex hull with other, less demanding regions.
Most of the reslts are negative. For synchronous systems, the submission shows that one can reduce the number of processes by replacing the requirment that the output lie in convex hull with the requirement that output lie in the convex hull of the per-axis projections of the inputs. Natural generalizations of the projection to sets of axes do not reduce the number of processes.
There is also no benefit in allowing the output to lie within any constant \delta of the xonvex hull. Some improvement is possible if \delta can depend on the inputs.
NOTES
In Figure 1(b), p is used in 2 distinct senses.
----------------------- REVIEW 2 ---------------------
PAPER: 46
TITLE: Relaxed Byzantine Vector Consensus
AUTHORS: Zhuolun Xiang and Nitin H. Vaidya
----------- Review -----------
In the Byzantine Vector Consensus problem, each process obtains a vector id d-dimensional space as input and all non-faulty processes must output the same vector, which falls within the convex hull of the input vectors of non-faulty processes. Previous work has studied an approximate version of this problem, where the agreement property is relaxed. Here, the authors instead consider relaxations of the validity property. In one, the common output vector must be within a distance delta of the convex hull. In the other, it is required that when the vectors are projected down to any k dimensions, the output falls within the convex hull of the inputs. (The paper also considers, very briefly, versions of the problem where both agreement and validity are relaxed.)
The authors study the problem in a synchronous model where f of the processes may experience Byzantine failures. The authors show that in some cases the relaxation does not make the problem any easier to solve than the exact version, while in other cases, the relaxation can be solved to tolerate a larger fraction of faulty processes. See page 3 for a statement of the results proved.
The algorithms presented are quite simple, but substantial analyses are required to prove them correct. The impossibility results (Theorem 4 and 11) are relatively straightforward, relying on a clever choice of input vectors. (Incidentally, I think the proof of Theorem 11 is more interesting than that of Theorem 4, so I would prefer to see 11 given in the body and 4 given in the appendix; this might require swapping Section 4 and 5, though.)
One major drawback of the paper is that there is no attempt made to motivate the relaxed problems that are introduced. It would be nice to see at least some example application where they might be used.
For the (delta,p)-relaxed version of the problem, it's not clear that a constant delta makes much sense: if this problem could be solved, it seems that one could also make delta arbitrarily small simply by multiplying all the input coordinates by some very large number M, solving the problem, and then dividing the output coordinates by M. The version of the problem where delta is dependent on the inputs makes much more sense to me.
Section 6, which deals with the versions of the problem where both the agreement and validity property are relaxed seems rather rushed, and even the (lengthy!) appendix has scant details on the material of Section 6. (For example, scanning the proof sketch of Theorem 13 in the appendix, I can't find the definition of kappa, which is used in the statement of Theorem 13.)
The paper is generally quite well-written. I expect that a talk on this topic could be quite nice too because a lot of the geometric proofs could be illustrated with nice diagrams.
Minor comments for authors:
p.4, line 1: delete second "problem"
Sec 3: Perhaps define L_infinity norm, since you use it later.
Sec 3, line 11: "Size" -> "The size"
p.6, line -5: "weight" -> "weights"
Sec 4.4, line 2: "then" -> "then the"
p.8, Step 2, line 3: "identical" -> "the same"
Lemma 7: "d <= 2" -> "d >= 2" on line 1. On line 2, perhaps it should be mentioned before the statement of the lemma why such an inscribed sphere exists.
p.10, line -7: "perserving" -> "preserving"
p.11, line 8: "denote" -> "denotes"
p.11, Case 2, line 2: "these exists" -> "there exist"
Defn 10: "k-relaxed" -> "The $k$-relaxed"
p. 13, line -3: "When" -> "For", "become" -> "becomes"
Bibliography: Capitalize "byzantine" (twice)
p.22, line -3: add a citation for the inequality.
----------------------- REVIEW 3 ---------------------
PAPER: 46
TITLE: Relaxed Byzantine Vector Consensus
AUTHORS: Zhuolun Xiang and Nitin H. Vaidya
----------- Review -----------
This paper defines a weak form of consensus in a Byzantine model.
The paper starts from the observation that Byzantine vector consensus requires that non-faulty processes reach agreement on a decision (or output) that is in the convex hull of the inputs at the non-faulty processes.
It was shown that, for n processes with up to f Byzantine failures, when the inputs are d-dimensional
vectors of reals, n max (3f + 1; (d + 1)f + 1) is the tight bound for synchronous systems, and
n (d + 2)f + 1 is tight for approximate consensus in asynchronous systems.
The paper defines k-relaxed consensus by replacing the validity convex hull by a relaxed convex hull. Then the paper proves interesting bounds on the new variation.
I have already reviewed the paper for other conferences. It is solid, although the motivation is contrived
But I vote for acceptance
----------------------- REVIEW 4 ---------------------
PAPER: 46
TITLE: Relaxed Byzantine Vector Consensus
AUTHORS: Zhuolun Xiang and Nitin H. Vaidya
----------- Review -----------
For the Byzantine Vector Consensus problem ( the proposed values are d-dimensional vectors of reals and the decision value must be in the convex hull of the inputs of the correct processes) , it has been shown that n >= max ( 3f+1, ( d+1) f+1) is the tight bound to solve this problem for n processes with up to f byzantines failures in a synchronous system. This means that for a given number of processes, the upper bound on the number of faulty processes depend on the dimension of the input values.
To circumvent this result the authors propose two possible relaxations of this problem, by relaxing the agreement condition. In the first one, k-relaxed byzantine vector consensus the processes have to agree on a vector that is contained in the convex hull of the projections of the inputs ( may be outside of the convex hull of the inputs.
In the second one ( \delta, p) â€“relaxed the processes have to agree on a vector that is at distance at most \delta of the convex hull of the inputs.
The authors prove that their relaxed versions do not modify the bound n >= max ( 3f+1, ( d+1) f+1).
If \delta is a function of the inputs, the authors show that in some particular case (\delta, p) consensus can be achieved using a smaller number of processes . The improvement concerns the case 3f+1 <= n <= d+1.
The contribution of this paper is weak. There is no motivation that the two relaxations are interesting by themselves. The first one does not allow to get a better bound than the initial problem and the improvement given by the second one is very limited.