Byzantine Fault-Tolerance in Decentralized Optimization under 2f-Redundancy

This paper considers the problem of exact Byzantine fault-tolerance in multi-agent decentralized optimization. We consider a complete peer-to-peer network of n agents; each agent has a local cost function, however, up to f of the agents are Byzantine faulty. Such faulty agents may not follow a prescribed algorithm correctly, and may share arbitrary incorrect information about their costs. The goal of the exact fault-tolerance problem is to design a decentralized algorithm that allows all the non-faulty agents to compute a common minimum point of only non-faulty agents' aggregate cost function. We propose the first-ever decentralized algorithm with provable exact fault-tolerance against a bounded fraction of faulty agents, provided the non-faulty agents have the necessary property named 2f-redundancy, defined later in the paper.