### Relaxed Byzantine Vector Consensus

**2016-01-29**

1601.08067 | cs.DC

Exact Byzantine consensus problem 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 is well-known that exact consensus is impossible
in an asynchronous system in presence of faults, and in a synchronous system,
n>=3f+1 is tight on the number of processes to achieve exact Byzantine
consensus with scalar inputs, in presence of up to f Byzantine faulty
processes. Recent work has shown that when the inputs are d-dimensional vectors
of reals, n>=max(3f+1,(d+1)f+1) is tight to achieve exact Byzantine consensus
in synchronous systems, and n>= (d+2)f+1 for approximate Byzantine 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 consider two relaxed versions of
Byzantine vector consensus: k-Relaxed Byzantine vector consensus and
(delta,p)-Relaxed Byzantine vector consensus. In k-relaxed consensus, the
validity condition requires that the output must be in the convex hull of
projection of the inputs onto any subset of k-dimensions of the vectors. For
(delta,p)-consensus the validity condition requires that the output must be
within distance delta of the convex hull of the inputs of the non-faulty
processes, where L_p norm is used as the distance metric. For
(delta,p)-consensus, we consider two versions: in one version, delta is a
constant, and in the second version, delta is a function of the inputs
themselves.
We show that for k-relaxed consensus and (delta,p)-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 delta depends on the
inputs, we show that the bound on n is smaller when d>=3.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-02-09**

1902.03498 | cs.LG

We show that fundamental learning tasks, such as finding an approximate
linear separator or linear r… show more

**2019-02-22**

1902.08559 | cs.DS

We consider the $k$-Clustering problem, which is for a given multiset of $n$
vectors $X\subset \math… show more

**2018-12-19**

1812.07769 | cs.DS

Semidefinite programming is a powerful tool in the design and analysis of
approximation algorithms f… show more

**2018-07-23**

1807.08446 | cs.LG

We suggest a new optimization technique for minimizing the sum $\sum_{i=1}^n
f_i(x)$ of $n$ non-conv… show more

**2019-02-27**

1902.10407 | cs.LG

The $\ell_p$ linear regression problem is to minimize $f(x)=||Ax-b||_p$ over
$x\in\mathbb{R}^d$, whe… show more

**2018-11-04**

1811.01421 | cs.DC

We prove that a class of fundamental shared memory tasks are not amenable to
certain standard proof … show more

**2018-02-18**

1802.06464 | cs.CV

Robust model fitting plays a vital role in computer vision, and research into
algorithms for robust … show more

**2018-08-20**

1808.06407 | cs.CC

Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with
profound connections to … show more

**2016-04-06**

1604.01482 | math.CO

Let $n$ be any positive integer and $\mathcal{F}$ be a family of subsets of
$[n]$.
A family $\math… show more

**2018-07-18**

1807.07156 | cs.DS

We provide a randomized linear time approximation scheme for a generic
problem about clustering of b… show more

**2018-04-19**

1804.07209 | cs.NE

This paper introduces Non-Autonomous Input-Output Stable Network (NAIS-Net),
a very deep architectur… show more

**2016-08-10**

1608.03245 | cs.CG

Every graph $G$ can be represented by a collection of equi-radii spheres in a
$d$-dimensional metric… show more

**2018-06-22**

1806.08725 | math.MG

We prove a no-dimensional version of Carath\'edory's theorem: given an
$n$-element set $P\subset \Re… show more

**2018-09-12**

1809.04355 | cs.DS

In real-time systems, in addition to the functional correctness recurrent
tasks must fulfill timing … show more

**2016-11-03**

1611.01146 | math.OC

We design a non-convex second-order optimization algorithm that is guaranteed
to return an approxima… show more

**2017-08-08**

1708.02543 | cs.DC

An algorithm for $n-1$-strong-equillibrium for distributed consensus in a
ring with rational agents … show more