cs.DCNov 9, 2026

DeFSM: Robust and Efficient Decentralization of Federated Submodular Maximization

Authors: Duc A. Tran, Dung Truong, Duy Le

Organizations: Department of Computer Science, University of Massachusetts Boston, Boston, MA, USA

Abstract

Submodular maximization seeks a small subset best representing a large dataset. In its federated setting, the server is a single point of failure and some clients may be Byzantine. Removing the server raises a trilemma of decentraliza- tion, efficiency, and security. We propose DeFSM, a Byzantine-robust and communication-efficient architecture that replaces the server with a lightweight smart contract and a pool of independent, consensus-free agents. Its aggregation rule, SafeGM, builds on two notions from combinatorial geometry: Tukey depth and safe points (the points lying in the convex hull of the good points wherever the bad points are). SafeGM makes the robust decision on 2D Gaussian random projections, which the contract can compute efficiently, and lifts it back as a convex combination of actual updates. Since lifting loses information, it uses the projected geometric median only when its depth certifies it, and otherwise a Tukey median. The share of bad updates is then bounded only by a count: how many there are, not what they contain. We prove, and confirm empirically, that this bound controls the solution quality. On CIFAR10 and PathMNIST, with up to 30% Byzantine clients and agents, DeFSM never collapses and retains on average about 91% of the quality of the ideal reference, the geometric median at a trusted central server. The geometric median decentralized in its best setting would retain about 96%, but the contract cannot compute it, and so each agent would have to download six times more data, or each client twice as much.

Figures & tables

Explore similar work

CardsList
  1. SWB-DM: A Calibrated Sliced-Wasserstein-Barycenter Aggregator with Delayed-Momentum Caching for Byzantine-Robust Federated Learning under Partial Participation

    Sep 14, 2026Saranraj S, Saranya M S, Alex David S +1Federated Learning AggregationByzantine-Robust Federated Learning

  2. Practical Validity Conditions for Byzantine-Tolerant Federated Learning

    May 15, 2026Mélanie Cambus, Darya Melnyk, Tijana Milentijević +1Federated Learning AggregationByzantine-Robust Federated Learning