ML p(r)ior | Relaxed Byzantine Vector Consensus

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.
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-02-22

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

Highlights - Most important sentences from the article

2018-12-19

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-11-04

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-08-20

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

Highlights - Most important sentences from the article

2016-04-06

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

Highlights - Most important sentences from the article

2018-07-18

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

Highlights - Most important sentences from the article

2018-04-19

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

Highlights - Most important sentences from the article

2016-08-10

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

Highlights - Most important sentences from the article

2018-06-22

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

Highlights - Most important sentences from the article

2018-09-12

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

Highlights - Most important sentences from the article

2016-11-03

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article