Network-aware mechanisms for tolerating Byzantine failures in distributed systems

Liang, Guanfeng

Permalink

https://hdl.handle.net/2142/31012 Copy

Description

Title

Network-aware mechanisms for tolerating Byzantine failures in distributed systems

Author(s)

Liang, Guanfeng

Issue Date

2012-05-22T00:21:32Z

Director of Research (if dissertation) or Advisor (if thesis)

Vaidya, Nitin H.

Doctoral Committee Chair(s)

Vaidya, Nitin H.

Committee Member(s)

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

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

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.

Graduation Semester

2012-05

Permalink

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

Copyright and License Information

Copyright 2012 Guanfeng Liang

Owning Collections