Papers › Byzantine Multi-Agent Optimization: Part I
Byzantine Multi-Agent Optimization: Part I
Lili Su, Nitin Vaidya
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We study Byzantine fault-tolerant distributed optimization of a sum of convex (cost) functions with real-valued scalar input/ouput. In particular, the goal is to optimize a global cost function 1/(|𝒩|)∑_(i∈𝒩) hᵢ(x), where 𝒩 is the set of non-faulty agents, and hᵢ(x) is agent i's local cost function, which is initially known only to agent i. In general, when some of the agents may be Byzantine faulty, the above goal is unachievable, because the identity of the faulty agents is not necessarily known to the non-faulty agents, and the faulty agents may behave arbitrarily. Since the above global cost function cannot be optimized exactly in presence of Byzantine agents, we define a weaker version of the problem. The goal for the weaker problem is to generate an output that is an optimum of a function formed as a convex combination of local cost functions of the non-faulty agents. More precisely, for some choice of weights αᵢ for i∈𝒩 such that αᵢ≥0 and ∑_(i∈𝒩)αᵢ=1, the output must be an optimum of the cost function ∑_(i∈𝒩) αᵢhᵢ(x). Ideally, we would like αᵢ=1/(|𝒩|) for all i∈𝒩 -- however, this cannot be guaranteed due to the presence of faulty agents. In fact, we show that the maximum achievable number of nonzero weights (αᵢ's) is |𝒩|-f, where f is the upper bound on the number of Byzantine agents. In addition, we present algorithms that ensure that at least |𝒩|-f agents have weights that are bounded away from 0. We also propose a low-complexity suboptimal algorithm, which ensures that at least ⌈n/2⌉-ϕ agents have weights that are bounded away from 0, where n is the total number of agents, and ϕ (ϕ≤f) is the actual number of Byzantine agents.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections