{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/101234"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/101234","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Exact Byzantine consensus under local-broadcast channels","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.","abstract_html":"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.","abstract_has_math":true,"creators":["Naqvi, Syed Shalan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Vaidya, Nitin"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-09-04T20:41:59Z","date_published":"2018-09-04T20:41:59Z","updated_at":"2026-07-22T22:24:38Z","subjects":["Consensus","Distributed Algorithms"],"languages":["en"],"rights":["Copyright 2018 Syed Shalan Naqvi"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/101234","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Vaidya, Nitin"]},{"key":"dc:creator","label":"Author","values":["Naqvi, Syed Shalan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-09-04T20:41:59Z","2020-09-05T09:15:29Z","2018-04-26","2018-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"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","Distributed Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2018 Syed Shalan Naqvi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/101234"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2020-05-01","The student, Syed Shalan Naqvi, accepted the attached license on 2018-04-26 at 03:23.","The student, Syed Shalan Naqvi, submitted this Thesis for approval on 2018-04-26 at 03:29.","This Thesis was approved for publication on 2018-04-26 at 15:20.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12513 on 2018-08-31 at 17:21:39","Made available in DSpace on 2018-09-04T20:41:59Z (GMT). No. of bitstreams: 2 NAQVI-THESIS-2018.pdf: 428422 bytes, checksum: 0f8db01f0775480d5125485b89a7b0c4 (MD5) LICENSE.txt: 4214 bytes, checksum: ac2a217270233963ff97e500b56a1bb3 (MD5) Previous issue date: 2018-04-26","Embargo set by: Seth Robbins for item 107319 Lift date: 2020-09-04T20:42:08Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 107319 on 2020-09-05T09:15:29Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Exact Byzantine consensus under local-broadcast channels"]}]}],"canonical_facts":{"dc:contributor":["Vaidya, Nitin"],"dc:creator":["Naqvi, Syed Shalan"],"dc:date":["2018-09-04T20:41:59Z","2020-09-05T09:15:29Z","2018-04-26","2018-05"],"dc:description":["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.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2020-05-01","The student, Syed Shalan Naqvi, accepted the attached license on 2018-04-26 at 03:23.","The student, Syed Shalan Naqvi, submitted this Thesis for approval on 2018-04-26 at 03:29.","This Thesis was approved for publication on 2018-04-26 at 15:20.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12513 on 2018-08-31 at 17:21:39","Made available in DSpace on 2018-09-04T20:41:59Z (GMT). No. of bitstreams: 2 NAQVI-THESIS-2018.pdf: 428422 bytes, checksum: 0f8db01f0775480d5125485b89a7b0c4 (MD5) LICENSE.txt: 4214 bytes, checksum: ac2a217270233963ff97e500b56a1bb3 (MD5) Previous issue date: 2018-04-26","Embargo set by: Seth Robbins for item 107319 Lift date: 2020-09-04T20:42:08Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 107319 on 2020-09-05T09:15:29Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/101234"],"dc:language":["en"],"dc:rights":["Copyright 2018 Syed Shalan Naqvi"],"dc:subject":["Consensus","Distributed Algorithms"],"dc:title":["Exact Byzantine consensus under local-broadcast channels"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:38Z"}