The problem of distributed (or collaborative) optimization in multi-agent systems has gained significant attention in recent years. In this problem, we have mutliple agents in the system and each agent knows its own local cost (or loss) function. In the fault-free setting, all the agents are non-faulty (or honest), and the goal is to design a distributed algorithm that enables the agents to compute a minimum of the aggregate of their local cost functions.
As a simple example, the local cost function for an agent (which may be a robot or a person) could be the cost to travel to a desired location from its current location. In that case, the minimum of the aggregate cost functions of all the agents is a location that minimizes the total cost of travel for all the agents. Such multi-agent distributed optimization is of interest in many practical applications, including distributed (or federated) machine learning, swarm robotics, and distributed control systems such as SCADA. Most of the prior work assumes all the agents to be non-faulty. Non-faulty agents follow a specified algorithm correctly. However, in practice some of the agents in the system may be faulty and may behave incorrectly.
We particularly consider a scenarion where some of the agents in the system are Byzantine faulty. The concept of Byzantine faults was first introduced by Leslie Lamport (and colleagues) in his seminal work on The Byzantine Generals Problem in 1982. The Byznatine faulty agents may send incorrect and inconsistent information in order to bias the output of a distributed optimization algorithm, and the faulty agents may also collude to optimize damage to the system. For example, consider an application of distributed optimization to the case of distributed sensing where the agents acting as sensors are observing a common object in order to collaboratively identify the object. However, the faulty agents may send arbitrary observations concocted to prevent the honest agents from making the correct identification. Similarly, in the case of distributed machine learning, which is another application of distributed optimization, the faulty agents may send incorrect information based on mislabelled or arbitrarily concocted data points to prevent the honest agents from learning a good classifier.
Pre-prints and publications: