## Files in this item

FilesDescriptionFormat

application/pdf

NAQVI-THESIS-2018.pdf (428kB)
(no description provided)PDF

## Description

 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 Degree: M.S. Genre: Thesis Subject(s): Consensus 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 Type: Text URI: http://hdl.handle.net/2142/101234 Rights Information: Copyright 2018 Syed Shalan Naqvi Date Available in IDEALS: 2018-09-042020-09-05 Date Deposited: 2018-05
﻿