==========
Notification for Brief Announcement: 122
Title: Brief Announcement: Relaxed Byzantine Vector Consensus:
==========
We are happy to inform you that your paper has been accepted to SPAA 2016 as a brief announcement. We received a large number of excellent submissions, and are expecting a great SPAA conference program.
Brief announcements did not receive full detailed reviews. Instead, we focused primarily on the question of whether it would be interesting to the SPAA audience. However, each brief announcement was read by several PC members, and I have attached below any comments that they had.
Recall that a brief announcement will receive two pages in the proceedings. We will be sending further information shortly on how to prepare and submit the camera-ready version of your paper.
Take care,
Seth (and the SPAA 2016 PC)
----------------------- REVIEW 1 ---------------------
PAPER: 122
TITLE: Brief Announcement: Relaxed Byzantine Vector Consensus
AUTHORS: Zhuolun Xiang and Nitin Vaidya
----------- Review -----------
The paper presents a new version of the Byzantine vector consensus, relaxing the conditions. Then, it claims a few results in the new problem.
I think the new problem defintion could be of interest to the SPAA community (although possibly PODC woudl have been a better fit).
----------------------- REVIEW 2 ---------------------
PAPER: 122
TITLE: Brief Announcement: Relaxed Byzantine Vector Consensus
AUTHORS: Zhuolun Xiang and Nitin Vaidya
----------- Review -----------
In the Byzantine vector consensus problem, introduced in recent (PODC13 and STOC13) papers, the processors should agree on a vector in the convex hull of their inputs. Known bounds, relating the number of processors n, maximum number of faults f, and the dimension of the vectors d, state that n \geq (d + 1) f + 1 (for sufficiently large d). This BA suggests two relaxed versions of the Byzantine vector consensus problem:
(1) In the k-relaxed Byzantine vector consensus problem, the output should be in the convex hull of every k-dimensional projection of the (d-dimensional) input vectors.
(2) In the (\delta, p)-relaxed Byzantine vector consensus, the distance of the output vector to the convex hull of the input vectors should be at most \delta, where the distance is measured according to the L_p norm.
The authors show that relaxation (1) does not change the aforementioned bound. For relaxation (2), the authors show that if \delta is fixed (independent of the parameters of the problem), then the aforementioned bound remains. However, if \delta may depend on n, f, d, p, and the maximum L_p distance between the input vectors, then the aforementioned bound can be broken.
Why do I want to include this BA in SPAA's program?
- An interesting problem that received some attention recently.
- Introducing fairly natural relaxations in attempt to achieve improved bounds.