Files in this item



application/pdfNAQVI-THESIS-2018.pdf (428kB)
(no description provided)PDF


Title:Exact Byzantine consensus under local-broadcast channels
Author(s):Naqvi, Syed Shalan
Advisor(s):Vaidya, Nitin
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Distributed Algorithms
Abstract: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.
Issue Date:2018-04-26
Rights Information:Copyright 2018 Syed Shalan Naqvi
Date Available in IDEALS:2018-09-04
Date Deposited:2018-05

This item appears in the following Collection(s)

Item Statistics