@inproceedings{406a1be8404a4c9e8ea94a7f6ce0644f,
title = "Byzantine vector consensus in complete graphs",
abstract = "Consider a network of n processes, each of which has a d-dimensional vector of reals as its input. Each process can communicate directly with all the processes in the system; thus the communication network is a complete graph. All the communication channels are reliable and FIFO (first-in-first-out). • We prove that in a synchronous system, n ≥ max(3f+ 1, (d+1) f+1) is necessary and sufficient for achieving Byzantine vector consensus. • In an asynchronous system, it is known that exact consensus is impossible in presence of faulty processes. For an asynchronous system, we prove that n ≥ (d+ 2) f + 1 is necessary and sufficient to achieve approximate Byzantine vector consensus. Our sufficiency proofs are constructive. We prove sufficiency by providing explicit algorithms that solve exact BVC in synchronous systems, and approximate BVC in asynchronous systems.",
keywords = "Asynchronous and synchronous systems, Byzantine consensus, Vector inputs",
author = "Vaidya, \{Nitin H.\} and Garg, \{Vijay K.\}",
year = "2013",
month = jul,
day = "22",
doi = "10.1145/2484239.2484256",
language = "English (US)",
isbn = "9781450320658",
series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",
publisher = "Association for Computing Machinery",
pages = "65--73",
booktitle = "PODC 2013 - Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing",
address = "United States",
note = "2013 ACM Symposium on Principles of Distributed Computing, PODC 2013 ; Conference date: 22-07-2013 Through 24-07-2013",
}