Exact Byzantine consensus under local-broadcast channels

Consensus;Distributed Algorithms

Naqvi, Syed Shalan ; Vaidya ; Nitin

关键词: Consensus;    Distributed Algorithms;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/101234/NAQVI-THESIS-2018.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

We consider the problem of achieving exact consensus with Byzantine faults under a local-broadcast communication channel. We prove necessary and sufficient conditions on the underlying communication graph to achieve consensus. We show that under this model consensus is possible on undirected graphs that have $2f+1$ nodes and are $2f$-connected. In contrast, it is well known that with point-to-point links, achieving consensus requires at least $3f+1$ nodes and $2f + 1$ connectivity. We show a tight result for the case of a single fault, by proving that consensus is impossible on any undirected graph that has at most $1$ connectivity, and providing an algorithm for $2$-connected graphs with at least $3$ nodes. We give another algorithm for achieving consensus with at most $f$ faulty nodes, on arbitrary undirected graphs with $2f$ connectivity and $2f+1$ nodes. Additionally, we prove that consensus is impossible on any graph with connectivity less than $f+1$. We also show some necessity results for directed graphs. Finally, we present an example network that suggests that connectivity less than $2f$ may be sufficient in general.