Distributed consensus under local broadcast and local multicast communication models

Khan, Muhammad Samir

Permalink

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

Description

Title

Distributed consensus under local broadcast and local multicast communication models

Author(s)

Khan, Muhammad Samir

Issue Date

2022-04-20

Director of Research (if dissertation) or Advisor (if thesis)

Vaidya, Nitin H

Doctoral Committee Chair(s)

Vaidya, Nitin H

Committee Member(s)

• Chekuri, Chandra
• Ren, Ling
• Welch, Jennifer L

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2022-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2022 Muhammad Samir Khan

Owning Collections