Research
DeFSM: Robust and Efficient Decentralization of Federated Submodular Maximization
Federated submodular maximization lets many clients jointly pick a small, highly informative subset of a large dataset, but the standard protocol relies on a central server that is a single point of…

- arXiv
- 2611.11866
- Published
- 2026-11-09
- Authors
- Duc A. Tran, Dung Truong, Duy Le
AI summary
Overview
Research area: Federated submodular maximization (FSM), Byzantine-robust aggregation, and blockchain-based decentralization of machine learning.
Technical level: Advanced. The paper combines combinatorial optimization (submodular maximization, continuous greedy), combinatorial geometry (Tukey depth, centerpoint theorem, geometric and Tukey medians in the plane), linear programming, and smart-contract system design.
Scope: The paper proposes DeFSM, a server-less architecture for federated submodular maximization that replaces the central server with a lightweight smart contract plus a pool of independent, consensus-free agents, and introduces a Byzantine-robust aggregation rule, SafeGM, that decides in a random 2D projection and lifts the decision back to the full-dimensional update space.
What This Paper Is About
Federated submodular maximization lets many clients jointly pick a small, highly informative subset of a large dataset, but the standard protocol relies on a central server that is a single point of failure and assumes clients behave honestly. Removing that server creates a trilemma: decentralization, efficiency, and security are hard to achieve at once, because robust aggregators normally work on full high-dimensional vectors that a smart contract cannot afford to process.
The paper's goal is a system where no trusted server exists, some clients and some off-chain workers ("agents") may be Byzantine, and yet the quality of the final subset is provably controlled by only the number of bad updates rather than their content.
Key Contributions
-
A new server-less FSM architecture. DeFSM is described as the first FSM architecture without a trusted server. Aggregation is outsourced to a pool of independent agents (a role anyone, including a client, can take by posting a deposit), coordinated by a smart contract so light that it stores only hashes, seeds, and a few numbers per agent. Client updates are shared through IPFS, and each round the contract itself, not a vote among agents, makes the robust decision.
-
A provable robustness guarantee (SafeGM). The aggregation rule SafeGM bounds the share of bad updates in its output by how many bad updates there are, not by what they contain. This is proved in Lemma 1 and turned into an end-to-end solution-quality guarantee (Theorem 1 in the paper's Section 5), recovering the classical (1 − 1/e) approximation up to client heterogeneity.
-
Decentralization efficiency. Because SafeGM decides in a random 2D projection and lifts the decision back, the contract needs only two numbers per agent and a small linear program, and clients download only the few agent aggregates the contract selects. The paper states this makes classical depth-based robustness usable in high dimension for the first time.
-
Empirical evidence. 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 geometric median at a trusted central server.
Main Findings
- Quality retention under attack: On CIFAR10 and PathMNIST with up to 30% Byzantine clients and agents, DeFSM retains on average about 91% of the quality of the ideal reference, the geometric median computed at a trusted central server.
- Never collapses: DeFSM is reported never to collapse, even under extreme heterogeneity.
- Cost of the idealized alternative: Decentralizing the geometric median in its best setting would retain about 96%, but the smart contract cannot compute it, and each agent would have to download six times more data, or each client twice as much.
- Weaker baselines: The mean and trimmed mean sometimes fall much lower than DeFSM.
- Bounded bad share in the full space: Lemma 1 shows the depth of the chosen 2D point is at least ⌈n/3⌉, the capped linear program's optimal value is at most 1/D⁺, and the safety deficit of the lifted output is at most |C⁻|/D⁺ — at most three times the fraction of bad updates, regardless of what the bad updates contain or where their projections land.
- Depth test usually passes: In the experiments, the 2D geometric median reached depth ⌈n/3⌉ in about 96% of aggregations, so the Tukey-median fallback was rarely needed.
- No knowledge of the Byzantine rate required: Unlike Krum and trimmed-mean style rules, SafeGM needs no prior count of how many updates to discard; its tolerance adapts through the depth D⁺.
- No agent consensus needed: Agents never exchange messages to agree on an aggregate; the contract computes the deep point from 2D coordinates alone.
- Measured communication cost: With M = L = 20, r = 10, and d = 200, a client downloads on average 9.3 agent aggregates with 487 nonzero entries per round in total, about 4 KB.
- Evaluation details beyond the abstract: The supplied content is truncated before Section 6, so per-dataset objective values, full ablation tables and complete experimental settings are not reported here.
Methodology in Plain English
The work starts from the observation that a smart contract can verify logic but cannot handle high-dimensional vectors, so the robust part of the computation has to happen off-chain. The design keeps the decision on-chain but makes that decision tiny.
-
Filter and deduplicate. Any submitted update that is not a binary vector with exactly r ones is discarded, so a malicious client can only choose which r elements to select. Identical updates are collapsed to one copy so that coordinated attackers who all submit the same vector do not stack votes.
-
Project to two dimensions. All updates are mapped to 2D with a random Gaussian projection. Two dimensions are chosen deliberately: a Tukey median of n points costs O(n log n) expected time in the plane, and the plane tolerates a Byzantine rate up to 1/3 (the centerpoint theorem), higher than 1/(k+1) for k > 2 dimensions.
-
Depth test, then choose. Compute the geometric median of the projected points. If its depth is at least ⌈n/3⌉, use it; otherwise fall back to a Tukey median, which is guaranteed to have that depth.
-
Capped lifting back to the original space. Solve a small linear program that expresses the chosen 2D point as a convex combination of the projected updates, with every coefficient capped at 1/D. The lifted output is the same convex combination of the actual high-dimensional updates. The cap is what limits how much weight any single — potentially bad — update can carry.
-
Split the work between agents and the contract. Each round, the contract draws M agents at random from a registered pool with deposits. Each agent runs SafeGM on a random sample of L ≪ N clients and posts its aggregate to IPFS plus a hash on-chain. Agents then post only the 2D projection of their aggregate to the contract. The contract runs the same 2D depth test and capped lifting on those M points, producing convex coefficients. Because a basic solution of the linear program has at most three coefficients strictly between 0 and 1/D, at most D + 2 coefficients are positive, so clients download at most D + 2 agent aggregates.
-
Reconstruction and verification. Each client downloads only the selected aggregates, verifies hashes and the projection consistency check, and computes the global aggregate itself in fixed-point arithmetic, so all good clients get the same answer. Failed checks become fraud proofs that cause the contract to remove the agent's point and slash its deposit.
-
Fresh, unpredictable projections. Two new projections are used per round, seeded from public 32-byte seeds fixed by the contract only after the inputs they project have been committed. A malicious client therefore cannot place its projected point in the deep region, and a malicious agent cannot move its 2D point after the projection is known.
Why This Matters
Research impact. The paper reframes Byzantine robustness for federated optimization around safety — lying in the convex hull of good updates — rather than around distance to a majority, which attackers can manipulate. It connects depth-based robust statistics and Byzantine vector consensus, previously limited to very low dimensions, to high-dimensional federated aggregation by deciding in 2D projections and bounding the lifting error. It also provides what it describes as the first Byzantine-robust, server-less FSM design, and the first use of blockchain for FSM.
Real-world applications (drawn from the application areas the paper lists for submodular maximization):
- Selecting the most informative unlabeled images for annotation, reducing labeling labor on edge devices.
- Feature selection for predictive analytics over data generated by distributed devices.
- Exemplar-based clustering and document summarization over data that cannot be centralized.
- Sensor placement and robotic data collection, where bandwidth and central-server capacity are constrained.
Industry relevance. Any deployment that wants federated data selection without operating a trusted aggregator — consortium settings, multi-organization data markets, or edge fleets where a central server is a single point of failure — maps directly onto the DeFSM design. The paper emphasizes that the contract is light enough for any blockchain to host, storing O(N + M) independent of the update dimension d, which addresses the practical gas and storage limits that have held back blockchain-based federated learning designs.
Future Directions
- Exact safety in high dimension. The paper explicitly does not claim exact safety in R^d; it targets a tractable proxy that is exact in 2D and bounds the loss on lifting. Closing that gap, or tightening the bound, is an open problem.
- General matroid constraints. The validity filter is described for the cardinality constraint in detail, with a note that for a general matroid the filter accepts indicators of bases checkable with an independence oracle; the analysis and empirical study of that setting are left open.
- Scaling and dataset breadth. The reported evaluation covers CIFAR10 and PathMNIST with M = L = 20, r = 10, d = 200. Behavior at larger agent pools, larger samples L, larger ground sets, and higher Byzantine rates approaching the 1/3 plane limit is a natural next question.
- Incentives and agent behavior. Agents register by posting a deposit and can be slashed via fraud proofs. How deposit sizing, pool composition, and rational (rather than purely Byzantine) agent behavior affect the guarantee is not resolved in the supplied content.
Target Audience
Graduate students and researchers in federated learning, distributed optimization, and blockchain systems who want a rigorous treatment of Byzantine robustness without a trusted server; practitioners designing decentralized or consortium-scale data-selection pipelines who need to know the communication and on-chain storage costs; and readers interested in how combinatorial-geometry tools such as Tukey depth and safe points can be made practical for high-dimensional machine learning.
Authors’ 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,…
The full abstract on arXiv