Exact Byzantine consensus under local-broadcast channels
Naqvi, Syed Shalan
Loading…
Permalink
https://hdl.handle.net/2142/101234
Description
Title
Exact Byzantine consensus under local-broadcast channels
Author(s)
Naqvi, Syed Shalan
Issue Date
2018-04-26
Director of Research (if dissertation) or Advisor (if thesis)
Vaidya, Nitin
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
