Brief announcement: Relaxed byzantine vector consensus

Zhuolun Xiang, Nitin H. Vaidya

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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. Recent work has 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. 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: k-relaxed Byzantine vector consensus and (δ,p)-relaxed Byzantine vector consensus. k-relaxed consensus only requires consensus for projections of inputs on every subset of k dimensions. (δ, p)-relaxed consensus requires that the output be within distance δ of the convex hull of the non-faulty inputs, where distance is defined using the Lp-norm. An input-dependent δ allows the distance from the non-faulty convex hull to be dependent on the maximum distance between the non-faulty inputs. We show that for k-relaxed consensus and (δ, p)-relaxed consensus with constant δ ≥ 0, the bound on n is identical to the bound stated above for the original vector consensus problem. On the other hand, when δ depends on the inputs, we show that the bound on n is smaller when d ≥ 3. Input-dependent δ may be of interest in practice - in essence, input-dependent δ scales with the spread of the inputs.

Original languageEnglish (US)
Title of host publicationSPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Number of pages3
ISBN (Electronic)9781450342100
StatePublished - Jul 11 2016
Event28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016 - Pacific Grove, United States
Duration: Jul 11 2016Jul 13 2016

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures


Other28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016
Country/TerritoryUnited States
CityPacific Grove


  • Byzantine consensus
  • Relaxed validity conditions
  • Vector inputs

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'Brief announcement: Relaxed byzantine vector consensus'. Together they form a unique fingerprint.

Cite this