Iterative Byzantine vector consensus in incomplete graphs

Nitin H. Vaidya

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

Abstract

This work addresses Byzantine vector consensus, wherein the input at each process is a d-dimensional vector of reals, and each process is required to decide on a decision vector that is in the convex hull of the input vectors at the fault-free processes [9,12]. The input vector at each process may also be viewed as a point in the d-dimensional Euclidean space Rd, where d > 0 is a finite integer. Recent work [9,12] has addressed Byzantine vector consensus, and presented algorithms with optimal fault tolerance in complete graphs. This paper considers Byzantine vector consensus in incomplete graphs using a restricted class of iterative algorithms that maintain only a small amount of memory across iterations. For such algorithms, we prove a necessary condition, and a sufficient condition, for the graphs to be able to solve the vector consensus problem iteratively. We present an iterative Byzantine vector consensus algorithm, and prove it correct under the sufficient condition. The necessary condition presented in this paper for vector consensus does not match with the sufficient condition for d > 1; thus, a weaker condition may potentially suffice for Byzantine vector consensus.

Original languageEnglish (US)
Title of host publicationDistributed Computing and Networking - 15th International Conference, ICDCN 2014, Proceedings
Pages14-28
Number of pages15
DOIs
StatePublished - 2014
Event15th International Conference on Distributed Computing and Networking, ICDCN 2014 - Coimbatore, India
Duration: Jan 4 2014Jan 7 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8314 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th International Conference on Distributed Computing and Networking, ICDCN 2014
CountryIndia
CityCoimbatore
Period1/4/141/7/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Iterative Byzantine vector consensus in incomplete graphs'. Together they form a unique fingerprint.

Cite this