{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/90567"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/90567","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Fault-tolerant consensus in directed graphs and convex hull consensus","abstract":"As distributed systems nowadays scale to thousands or more of nodes, fault-tolerance becomes one of the most important topics. This dissertation studies the fault-tolerance aspect of the consensus algorithm, which is a fundamental building block for the distributed systems. Particularly, the dissertation has the following two main contributions on fault-tolerant consensus in message-passing networks: • We explore various fault-tolerant consensus problems under different fault models in communication networks that are modeled as arbitrary directed graphs, i.e., two pairs of nodes may not share a bi- directional communication channel, and not every pair of nodes may be able to communicate with each other directly or indirectly. We prove the tight condition of the underlying communication graphs for solving each of the consensus problem, i.e., the necessary condition is equal to the sufficient condition. • We propose a new consensus problem – convex hull consensus – in which the input is a vector of reals in the d-dimensional space, and the output is a convex polytope contained within the convex hull of all inputs at fault-free nodes. For asynchronous systems, we present an approximate convex hull consensus algorithm with optimal fault tolerance that reaches consensus on optimal output polytope under crash fault model. Convex hull consensus may be used to solve related problems, such as vector consensus and function optimization with the initial convex hull as the domain.","abstract_html":"As distributed systems nowadays scale to thousands or more of nodes, fault-tolerance becomes one of the most important topics. This dissertation studies the fault-tolerance aspect of the consensus algorithm, which is a fundamental building block for the distributed systems. Particularly, the dissertation has the following two main contributions on fault-tolerant consensus in message-passing networks: • We explore various fault-tolerant consensus problems under different fault models in communication networks that are modeled as arbitrary directed graphs, i.e., two pairs of nodes may not share a bi- directional communication channel, and not every pair of nodes may be able to communicate with each other directly or indirectly. We prove the tight condition of the underlying communication graphs for solving each of the consensus problem, i.e., the necessary condition is equal to the sufficient condition. • We propose a new consensus problem – convex hull consensus – in which the input is a vector of reals in the d-dimensional space, and the output is a convex polytope contained within the convex hull of all inputs at fault-free nodes. For asynchronous systems, we present an approximate convex hull consensus algorithm with optimal fault tolerance that reaches consensus on optimal output polytope under crash fault model. Convex hull consensus may be used to solve related problems, such as vector consensus and function optimization with the initial convex hull as the domain.","abstract_has_math":false,"creators":["Tseng, Lewis"],"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","Gupta, Indranil","Welch, Jennifer L"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-07-07T19:54:10Z","date_published":"2016-07-07T19:54:10Z","updated_at":"2026-07-22T22:26:32Z","subjects":["Consensus","Byzantine fault","Crash fault","Directed network","fault-tolerance","convex hull consensus"],"languages":["en"],"rights":["Copyright 2016 Lewis Tseng"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/90567","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","Gupta, Indranil","Welch, Jennifer L"]},{"key":"dc:creator","label":"Author","values":["Tseng, Lewis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-07-07T19:54:10Z","2016-04-20","2016-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":["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","Crash fault","Directed network","fault-tolerance","convex hull consensus"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2016 Lewis Tseng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/90567"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["As distributed systems nowadays scale to thousands or more of nodes, fault-tolerance becomes one of the most important topics. This dissertation studies the fault-tolerance aspect of the consensus algorithm, which is a fundamental building block for the distributed systems. Particularly, the dissertation has the following two main contributions on fault-tolerant consensus in message-passing networks: • We explore various fault-tolerant consensus problems under different fault models in communication networks that are modeled as arbitrary directed graphs, i.e., two pairs of nodes may not share a bi- directional communication channel, and not every pair of nodes may be able to communicate with each other directly or indirectly. We prove the tight condition of the underlying communication graphs for solving each of the consensus problem, i.e., the necessary condition is equal to the sufficient condition. • We propose a new consensus problem – convex hull consensus – in which the input is a vector of reals in the d-dimensional space, and the output is a convex polytope contained within the convex hull of all inputs at fault-free nodes. For asynchronous systems, we present an approximate convex hull consensus algorithm with optimal fault tolerance that reaches consensus on optimal output polytope under crash fault model. Convex hull consensus may be used to solve related problems, such as vector consensus and function optimization with the initial convex hull as the domain.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-07-07 without embargo terms","The student, Lewis Tseng, accepted the attached license on 2016-04-18 at 16:54.","The student, Lewis Tseng, submitted this Dissertation for approval on 2016-04-18 at 17:01.","This Dissertation was approved for publication on 2016-04-20 at 10:04.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9315 on 2016-07-07 at 13:31:15","Made available in DSpace on 2016-07-07T19:54:10Z (GMT). No. of bitstreams: 3 TSENG-DISSERTATION-2016.pdf: 1426829 bytes, checksum: 3658205a55a72f476c1cdc7d775ba024 (MD5) LICENSE.txt: 4208 bytes, checksum: 0a3c6d9f66e0bde781187e19526487d8 (MD5) PROQUEST_LICENSE.txt: 4554 bytes, checksum: c0c724c64cea045c6364727940cb8078 (MD5) Previous issue date: 2016-04-20"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Fault-tolerant consensus in directed graphs and convex hull consensus"]}]}],"canonical_facts":{"dc:contributor":["Vaidya, Nitin H.","Chekuri, Chandra","Gupta, Indranil","Welch, Jennifer L"],"dc:creator":["Tseng, Lewis"],"dc:date":["2016-07-07T19:54:10Z","2016-04-20","2016-05"],"dc:description":["As distributed systems nowadays scale to thousands or more of nodes, fault-tolerance becomes one of the most important topics. This dissertation studies the fault-tolerance aspect of the consensus algorithm, which is a fundamental building block for the distributed systems. Particularly, the dissertation has the following two main contributions on fault-tolerant consensus in message-passing networks: • We explore various fault-tolerant consensus problems under different fault models in communication networks that are modeled as arbitrary directed graphs, i.e., two pairs of nodes may not share a bi- directional communication channel, and not every pair of nodes may be able to communicate with each other directly or indirectly. We prove the tight condition of the underlying communication graphs for solving each of the consensus problem, i.e., the necessary condition is equal to the sufficient condition. • We propose a new consensus problem – convex hull consensus – in which the input is a vector of reals in the d-dimensional space, and the output is a convex polytope contained within the convex hull of all inputs at fault-free nodes. For asynchronous systems, we present an approximate convex hull consensus algorithm with optimal fault tolerance that reaches consensus on optimal output polytope under crash fault model. Convex hull consensus may be used to solve related problems, such as vector consensus and function optimization with the initial convex hull as the domain.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-07-07 without embargo terms","The student, Lewis Tseng, accepted the attached license on 2016-04-18 at 16:54.","The student, Lewis Tseng, submitted this Dissertation for approval on 2016-04-18 at 17:01.","This Dissertation was approved for publication on 2016-04-20 at 10:04.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9315 on 2016-07-07 at 13:31:15","Made available in DSpace on 2016-07-07T19:54:10Z (GMT). No. of bitstreams: 3 TSENG-DISSERTATION-2016.pdf: 1426829 bytes, checksum: 3658205a55a72f476c1cdc7d775ba024 (MD5) LICENSE.txt: 4208 bytes, checksum: 0a3c6d9f66e0bde781187e19526487d8 (MD5) PROQUEST_LICENSE.txt: 4554 bytes, checksum: c0c724c64cea045c6364727940cb8078 (MD5) Previous issue date: 2016-04-20"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/90567"],"dc:language":["en"],"dc:rights":["Copyright 2016 Lewis Tseng"],"dc:subject":["Consensus","Byzantine fault","Crash fault","Directed network","fault-tolerance","convex hull consensus"],"dc:title":["Fault-tolerant consensus in directed graphs and convex hull consensus"],"dc:type":["text"],"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:26:32Z"}