{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/115474"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/115474","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Distributed consensus under local broadcast and local multicast communication models","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo terms","abstract_has_math":false,"creators":["Khan, Muhammad Samir"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Vaidya, Nitin H","Chekuri, Chandra","Ren, Ling","Welch, Jennifer L"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-05","date_published":"2022-05","updated_at":"2026-07-22T22:24:54Z","subjects":["consensus","Byzantine fault","fault-tolerance","distributed algorithm","broadcast","multicast"],"languages":["en","eng"],"rights":["Copyright 2022 Muhammad Samir Khan"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/115474","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Vaidya, Nitin H","Chekuri, Chandra","Ren, Ling","Welch, Jennifer L"]},{"key":"dc:creator","label":"Author","values":["Khan, Muhammad Samir"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-05","2022-04-20"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["consensus","Byzantine fault","fault-tolerance","distributed algorithm","broadcast","multicast"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2022 Muhammad Samir Khan"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/115474"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo terms","The student, Muhammad Khan, accepted the attached license on 2022-04-16 at 10:58.","The student, Muhammad Khan, submitted this Dissertation for approval on 2022-04-16 at 11:26.","This Dissertation was approved for publication on 2022-04-20 at 14:24.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17724 on 2022-11-11 at 13:15:29","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Distributed consensus under local broadcast and local multicast communication models"]}]}],"canonical_facts":{"dc:contributor":["Vaidya, Nitin H","Chekuri, Chandra","Ren, Ling","Welch, Jennifer L"],"dc:creator":["Khan, Muhammad Samir"],"dc:date":["2022-05","2022-04-20"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo terms","The student, Muhammad Khan, accepted the attached license on 2022-04-16 at 10:58.","The student, Muhammad Khan, submitted this Dissertation for approval on 2022-04-16 at 11:26.","This Dissertation was approved for publication on 2022-04-20 at 14:24.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17724 on 2022-11-11 at 13:15:29","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/115474"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Muhammad Samir Khan"],"dc:subject":["consensus","Byzantine fault","fault-tolerance","distributed algorithm","broadcast","multicast"],"dc:title":["Distributed consensus under local broadcast and local multicast communication models"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:54Z"}