Xiang, Zhuolun ;
Vaidya, Nitin H.
Relaxed Byzantine Vector Consensus
Abstract
Byzantine vector consensus requires that nonfaulty processes reach agreement on adecision (or output) that is in the convex hull of the inputs at the nonfaulty processes. Recent work has shown that, for n processes with up to f Byzantine failures, when the inputs are ddimensional 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.
Due to the dependence of the lower bound on vector dimension d, the number of processes necessary becomes large when the vector dimension is large. With the hope of reducing the lower bound on n, we propose relaxed versions of Byzantine vector consensus: krelaxed Byzantine vector consensus and (delta, p)relaxed Byzantine vector consensus. krelaxed consensus only requires consensus for projections of inputs on every subset of k dimensions. (delta, p)relaxed consensus requires that the output be within distance d of the convex hull of the nonfaulty inputs, where distance is defined using the L_{p}norm. An inputdependent delta allows the distance from the nonfaulty convex hull to be dependent on the maximum distance between the nonfaulty inputs.
We show that for krelaxed consensus with k > 1, and for (delta, p)relaxed consensus with constant delta >= 0, the bound on n is identical to the bound stated above for the original vector consensus problem. On the other hand, when k = 1 or d depends on the inputs, we show that the bound on n is smaller when d >= 3. Inputdependent delta may be of interest in practice. In essence, inputdependent delta scales with the spread of the inputs.
BibTeX  Entry
@InProceedings{xiang_et_al:LIPIcs:2017:7095,
author = {Zhuolun Xiang and Nitin H. Vaidya},
title = {{Relaxed Byzantine Vector Consensus}},
booktitle = {20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
pages = {26:126:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770316},
ISSN = {18688969},
year = {2017},
volume = {70},
editor = {Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7095},
URN = {urn:nbn:de:0030drops70958},
doi = {10.4230/LIPIcs.OPODIS.2016.26},
annote = {Keywords: Byzantine consensus, vector inputs, relaxed validity conditions}
}
06.04.2017
Keywords: 

Byzantine consensus, vector inputs, relaxed validity conditions 
Seminar: 

20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Issue date: 

2017 
Date of publication: 

06.04.2017 