Byzantine Fault-Tolerance in Decentralized Optimization under Minimal Redundancy
arXiv:2009.14763
Abstract
This paper considers the problem of Byzantine fault-tolerance in multi-agent decentralized optimization. In this problem, each agent has a local cost function. The goal of a decentralized optimization algorithm is to allow the agents to cooperatively compute a common minimum point of their aggregate cost function. We consider the case when a certain number of agents may be Byzantine faulty. Such faulty agents may not follow a prescribed algorithm, and they may share arbitrary or incorrect information with other non-faulty agents. Presence of such Byzantine agents renders a typical decentralized optimization algorithm ineffective. We propose a decentralized optimization algorithm with provable exact fault-tolerance against a bounded number of Byzantine agents, provided the non-faulty agents have a minimal redundancy.
arXiv commentAn extension of our prior work on fault-tolerant distributed optimization, for the server-based system architecture (https://dl.acm.org/doi/10.1145/3382734.3405748), to the more general peer-to-peer system architecture
References in corpus (7)
- Constrained Consensus
- Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance
- Byzantine-Resilient Distributed Optimization of Multi-Dimensional Functions
- Byzantine Fault Tolerant Distributed Linear Regression
- Finite-time Guarantees for Byzantine-Resilient Distributed State Estimation with Noisy Measurements
- Byzantine Fault-Tolerant Distributed Machine Learning Using Stochastic Gradient Descent (SGD) and Norm-Based Comparative Gradient Elimination (CGE)
- Resilience in Collaborative Optimization: Redundant and Independent Cost Functions