Distributed consensus under local broadcast and local multicast communication models

Byzantine consensus is a classical problem in distributed computing wherein n nodes want to reach agreement in the presence of up to f Byzantine faulty nodes. The nodes communicate with each other by passing messages. In the point-to-point communication model, the communication between nodes is modeled using a simple graph where each edge represents a point-to-point link between the two endpoints. All messages sent on an edge are private between the two endpoints of the edge. This allows a faulty node to equivocate, i.e., give inconsistent information to its neighbors. In this dissertation, we investigate Byzantine consensus under two communication models that weaken equivocation. 1) In the local broadcast model, the communication network is modeled using a simple graph. Every message transmitted by a node is received identically and correctly by all of its neighbors. In this model, a faulty node's attempt to equivocate is detected by its neighboring nodes. 2) In the local multicast model, the communication between nodes is modeled via a directed hypergraph. Each directed hyperedge captures a local multicast channel and is defined by a single sender and multiple receivers. Every message transmitted by a sender node on a local multicast channel is received identically and correctly by all the receiver nodes in the channel. The local multicast model generalizes both the point-to-point and local broadcast models, as well as the undirected hypergraph model considered in the literature. For the binary-valued Byzantine consensus problem, we obtain tight necessary and sufficient network conditions under local broadcast in undirected and directed graphs, as well as in the local multicast model.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Khan, Muhammad Samir

Contributors dc:contributor

• Vaidya, Nitin H
• Chekuri, Chandra
• Ren, Ling
• Welch, Jennifer L

• consensus
• Byzantine fault
• fault-tolerance
• distributed algorithm
• broadcast
• multicast

Statement dc:rights

• Copyright 2022 Muhammad Samir Khan

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/115474

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F115474