Defending distributed systems against adversarial attacks: consensus, consensus-based learning, and statistical learning

A distributed system consists of networked components that interact with each other in order to achieve a common goal. Given the ubiquity of distributed systems and their vulnerability to adversarial attacks, it is crucial to design systems that are provably secured. In this dissertation, we propose and explore the problems of performing consensus, consensus-based learning, and statistical learning in the presence of malicious components. (1) Consensus: In this dissertation, we explore the influence of communication range on the computability of reaching iterative approximate consensus. Particularly, we characterize the tight topological condition on the networks for consensus to be achievable in the presence of Byzantine components. Our results bridge the gap of previous work. (2) Consensus-Based Learning: We propose, to the best of our knowledge, consensus-based Byzantine-tolerant learning problems: Consensus-Based Multi-Agent Optimization and Consensus-Based Distributed Hypothesis Testing. For the former, we characterize the performance degradation, and design efficient algorithms that can achieve the optimal fault-tolerance performance. For the latter, we propose, as far as we know, the first learning algorithm under which the good agents can collaboratively identify the underlying truth. (3) Statistical Learning: Finally, we explore distributed statistical learning, where the distributed system is captured by the server-client model. We develop a distributed machine learning algorithm that is able to (1) tolerate Byzantine failures, (2) accurately learn a highly complex model with low local data volume, and (3) converge exponentially fast using logarithmic communication rounds.

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

2017

Author dc:creator

• Su, Lili

Contributors dc:contributor

• Vaidya, Nitin H.
• Attiya, Hagit
• Hajek, Bruce
• Srikant, R.

• Fault-tolerance
• Adversaries
• Security
• Consensus
• Optimization
• Hypothesis testing
• Statistical learning

Statement dc:rights

• Copyright 2017 Lili Su

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

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