{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/31012"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/31012","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Network-aware mechanisms for tolerating Byzantine failures in distributed systems","abstract":"Given the growing reliance of industry and government on online information services such as cloud computing and data centers, efficient fault-tolerance algorithm design is of increasing importance in both industry and academia. In this dissertation, we present some of our efficient fault-tolerant algorithms for distributed systems under both point-to-point and broadcast communication models. For the point-to-point model, we mainly consider Byzantine agreement algorithms. We develop algorithms that require only O(nL) total bits of communication for achieving agreement of L bits among n nodes for sufficiently large L, without making any cryptographic assumption. Previous algorithms either have higher communication cost or rely on cryptographic assumptions. We also develop Byzantine agreement algorithms that perform well when the communication links in the network are capacity-constrained. We develop the first Byzantine broadcast algorithm that achieves constant fraction of the optimal throughput in general point-to-point networks. For some special class of networks, we develop algorithms that achieve the optimal throughput. We then study the communication complexity of the multiparty equality function, which is the core of the Byzantine agreement problem. For the broadcast model, we study the problem of detecting packet tampering attacks in multi-hop wireless networks. We propose a lightweight detection scheme that integrates the idea of wireless watchdogs and error detection coding. We show in a single flow example that even if the watchdog can only observe a fraction of packets, by choosing the encoder properly, an attacker will be detected with high probability while achieving throughput arbitrarily close to optimal. The trade-off between throughput and security in a more practical setting – there are multiple data flows in the network and a distributed random access MAC protocol is used – is also studied.","abstract_html":"Given the growing reliance of industry and government on online information services such as cloud computing and data centers, efficient fault-tolerance algorithm design is of increasing importance in both industry and academia. In this dissertation, we present some of our efficient fault-tolerant algorithms for distributed systems under both point-to-point and broadcast communication models. For the point-to-point model, we mainly consider Byzantine agreement algorithms. We develop algorithms that require only O(nL) total bits of communication for achieving agreement of L bits among n nodes for sufficiently large L, without making any cryptographic assumption. Previous algorithms either have higher communication cost or rely on cryptographic assumptions. We also develop Byzantine agreement algorithms that perform well when the communication links in the network are capacity-constrained. We develop the first Byzantine broadcast algorithm that achieves constant fraction of the optimal throughput in general point-to-point networks. For some special class of networks, we develop algorithms that achieve the optimal throughput. We then study the communication complexity of the multiparty equality function, which is the core of the Byzantine agreement problem. For the broadcast model, we study the problem of detecting packet tampering attacks in multi-hop wireless networks. We propose a lightweight detection scheme that integrates the idea of wireless watchdogs and error detection coding. We show in a single flow example that even if the watchdog can only observe a fraction of packets, by choosing the encoder properly, an attacker will be detected with high probability while achieving throughput arbitrarily close to optimal. The trade-off between throughput and security in a more practical setting – there are multiple data flows in the network and a distributed random access MAC protocol is used – is also studied.","abstract_has_math":false,"creators":["Liang, Guanfeng"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Kumar, P.R.","Vaidya, Nitin H.","Chekuri, Chandra S.","Veeravalli, Venugopal V."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-05-22T00:21:32Z","date_published":"2012-05-22T00:21:32Z","updated_at":"2026-07-22T22:25:29Z","subjects":["Byzantine agreement","Consensus","Fault-Tolerance","Broadcast","Watchdog","Capacity","Distributed Algorithms","Distributed Systems","Equality"],"languages":["en"],"rights":["Copyright 2012 Guanfeng Liang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/31012","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kumar, P.R.","Vaidya, Nitin H.","Chekuri, Chandra S.","Veeravalli, Venugopal V."]},{"key":"dc:creator","label":"Author","values":["Liang, Guanfeng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-05-22T00:21:32Z","2012-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"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":["Byzantine agreement","Consensus","Fault-Tolerance","Broadcast","Watchdog","Capacity","Distributed Algorithms","Distributed Systems","Equality"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2012 Guanfeng Liang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/31012"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Given the growing reliance of industry and government on online information services such as cloud computing and data centers, efficient fault-tolerance algorithm design is of increasing importance in both industry and academia. In this dissertation, we present some of our efficient fault-tolerant algorithms for distributed systems under both point-to-point and broadcast communication models. For the point-to-point model, we mainly consider Byzantine agreement algorithms. We develop algorithms that require only O(nL) total bits of communication for achieving agreement of L bits among n nodes for sufficiently large L, without making any cryptographic assumption. Previous algorithms either have higher communication cost or rely on cryptographic assumptions. We also develop Byzantine agreement algorithms that perform well when the communication links in the network are capacity-constrained. We develop the first Byzantine broadcast algorithm that achieves constant fraction of the optimal throughput in general point-to-point networks. For some special class of networks, we develop algorithms that achieve the optimal throughput. We then study the communication complexity of the multiparty equality function, which is the core of the Byzantine agreement problem. For the broadcast model, we study the problem of detecting packet tampering attacks in multi-hop wireless networks. We propose a lightweight detection scheme that integrates the idea of wireless watchdogs and error detection coding. We show in a single flow example that even if the watchdog can only observe a fraction of packets, by choosing the encoder properly, an attacker will be detected with high probability while achieving throughput arbitrarily close to optimal. The trade-off between throughput and security in a more practical setting – there are multiple data flows in the network and a distributed random access MAC protocol is used – is also studied.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-03-29T18:59:36Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Liang_Guanfeng.pdf: 989543 bytes, checksum: 5d026fbe01750774132ce25d2c9d9a74 (MD5)","Made available in DSpace on 2012-05-22T00:21:32Z (GMT). No. of bitstreams: 2 Liang_Guanfeng.pdf: 989543 bytes, checksum: 5d026fbe01750774132ce25d2c9d9a74 (MD5) license.txt: 4063 bytes, checksum: 53dbb5d28605cb838ca17782b1b80319 (MD5)"]},{"key":"dc:title","label":"Title","values":["Network-aware mechanisms for tolerating Byzantine failures in distributed systems"]}]}],"canonical_facts":{"dc:contributor":["Kumar, P.R.","Vaidya, Nitin H.","Chekuri, Chandra S.","Veeravalli, Venugopal V."],"dc:creator":["Liang, Guanfeng"],"dc:date":["2012-05-22T00:21:32Z","2012-05"],"dc:description":["Given the growing reliance of industry and government on online information services such as cloud computing and data centers, efficient fault-tolerance algorithm design is of increasing importance in both industry and academia. In this dissertation, we present some of our efficient fault-tolerant algorithms for distributed systems under both point-to-point and broadcast communication models. For the point-to-point model, we mainly consider Byzantine agreement algorithms. We develop algorithms that require only O(nL) total bits of communication for achieving agreement of L bits among n nodes for sufficiently large L, without making any cryptographic assumption. Previous algorithms either have higher communication cost or rely on cryptographic assumptions. We also develop Byzantine agreement algorithms that perform well when the communication links in the network are capacity-constrained. We develop the first Byzantine broadcast algorithm that achieves constant fraction of the optimal throughput in general point-to-point networks. For some special class of networks, we develop algorithms that achieve the optimal throughput. We then study the communication complexity of the multiparty equality function, which is the core of the Byzantine agreement problem. For the broadcast model, we study the problem of detecting packet tampering attacks in multi-hop wireless networks. We propose a lightweight detection scheme that integrates the idea of wireless watchdogs and error detection coding. We show in a single flow example that even if the watchdog can only observe a fraction of packets, by choosing the encoder properly, an attacker will be detected with high probability while achieving throughput arbitrarily close to optimal. The trade-off between throughput and security in a more practical setting – there are multiple data flows in the network and a distributed random access MAC protocol is used – is also studied.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-03-29T18:59:36Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Liang_Guanfeng.pdf: 989543 bytes, checksum: 5d026fbe01750774132ce25d2c9d9a74 (MD5)","Made available in DSpace on 2012-05-22T00:21:32Z (GMT). No. of bitstreams: 2 Liang_Guanfeng.pdf: 989543 bytes, checksum: 5d026fbe01750774132ce25d2c9d9a74 (MD5) license.txt: 4063 bytes, checksum: 53dbb5d28605cb838ca17782b1b80319 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/31012"],"dc:language":["en"],"dc:rights":["Copyright 2012 Guanfeng Liang"],"dc:subject":["Byzantine agreement","Consensus","Fault-Tolerance","Broadcast","Watchdog","Capacity","Distributed Algorithms","Distributed Systems","Equality"],"dc:title":["Network-aware mechanisms for tolerating Byzantine failures in distributed systems"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:29Z"}