Network-aware mechanisms for tolerating Byzantine failures in distributed systems

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2012

Author dc:creator

• Liang, Guanfeng

Contributors dc:contributor

• Kumar, P.R.
• Vaidya, Nitin H.
• Chekuri, Chandra S.
• Veeravalli, Venugopal V.

• Byzantine agreement
• Consensus
• Fault-Tolerance
• Broadcast
• Watchdog
• Capacity
• Distributed Algorithms
• Distributed Systems
• Equality

Statement dc:rights

• Copyright 2012 Guanfeng Liang

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/31012

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/31012