CS Paper Radar

DeFSM: Robust and Efficient Decentralization of Federated Submodular Maximization

Duc A. Tran, Dung Truong, Duy Le

cs.DC cs.LG ·submitted 2026-11-09 04:43 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Byzantine-resilient Federated Learning with User-level Differential Privacy

cs.LG cs.DCmath.OC ·2026-11-07 ·Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong, Lili Su
publishedtheory similarity 0.66
Abstract · NeurIPS 2026

Real-world deployment of federated learning (FL) requires resilience against adversarial clients and data privacy. Byzantine fault captures the worst-case behavior of adversarial clients, while differential privacy (DP) provides statistical guarantees against privacy loss. In particular, user-level DP guards a client's entire contribution and provides more realistic protection against information leakage. Despite intensive efforts, the minimax-optimal convergence bound of Byzantine-resilient FL with user-level DP remains open. We establish an information-theoretic lower bound for any Byzantine-resilient empirical risk minimization problem under user-level DP and heterogeneous clients. We propose ByzULDP, a central DP algorithm featuring a two-level momentum across the client and server. Client-side momentum mitigates stochastic gradient variance during robust aggregation. Unlike the fault-free case, naively combining non-linear Byzantine-resilient aggregation with central DP noise can be insufficient to guarantee convergence to a bounded neighborhood of a stationary point. Our key contribution is a server-side momentum that leverages a property specific to user-level DP, where privacy sensitivity depends on how client updates are constructed, to empower convergence. ByzULDP achieves the order-optimal convergence bound for strongly-convex objectives, with vanishing error terms decaying at the optimal $O(1/T)$ and $O(1/\sqrt{T})$ rates for strongly-convex and non-convex objectives, respectively. We corroborate our analysis with numerical experiments on real-world datasets across diverse privacy budgets.

0.14

Beyond Leaderless: Randomized Consensus Against Mobile Crashes

cs.DC ·2026-10-31 ·Ittai Abraham, Kaya Alpturer, Pranav Garimidi, Joachim Neu, Tim Roughgarden +1 more
similarity 0.64
Abstract · 32 pages, 6 figures

Many consensus protocols fail to terminate under attack from an adversary that has the power to move between replicas and repeatedly crash one of them, even in synchrony. We present Multi-Leader Fixed-View Simplex (ML-FVS) to defend against such an adversary while keeping the simple structure and good-case latency of Simplex consensus. Our protocol extends fixed-view Simplex with multiple leaders, each of which may broadcast a proposal. At the voting deadline, each replica votes on the set of proposals it has seen so far. A hidden threshold beacon revealed after the votes gives a priority order on the multiple leaders, resolving each vote to its highest-priority proposal. Our model combines permanent adaptive Byzantine faults with mobile crashes. For a constant crash budget and $Δ$-delayed Byzantine corruption, we obtain $O(Δ)$ expected latency over repeated views whose leaders start honest. With immediate Byzantine corruptions, the protocol still achieves liveness. We also evaluate the protocol under random network delays and stochastic faults, finding that multiple leaders reduce view failures even when rational leaders delay their proposals to increase rewards.

0.19

Improving the Robustness of the XRP Ledger Network via Edge Augmentation Strategies

cs.CR ·2026-08-26 ·Afonso Vilalonga, Orkun İrsoy, João S. Resende, Henrique Domingos, Osman Yağan
similarity 0.64
Abstract

The XRP Ledger allows its network participants to select a set of trusted peers within the network (i.e., the Unique Node List (UNL)) and communicate with them to reach consensus on which transactions should be included in the next ledger state. However, its consensus protocol requires significant overlap among participants' UNLs, along with a high agreement threshold among the nodes within each UNL (e.g., 80\%). Consequently, an attacker could disrupt the consensus process in such a network by targeting the nodes that form the network's connectivity backbone and reducing the number of trusted participants that can communicate with one another below the required threshold. In this paper, we evaluate strategies to improve the robustness of the XRP Ledger's existing topology, as measured by our formal definitions of quorum and network robustness, and compare them to a second strategy from prior work. The strategy we present is an addition/augmentation approach, in which new edges are added based on different constructions. The second strategy is a rewiring or edge-replacement approach, in which the overall number of edges is preserved but they are rearranged. For each strategy, we consider two different cases: one in which all nodes participate in the edge construction or rewiring process, and another in which only a subset of nodes participates. Our findings demonstrate substantial improvements in robustness when augmentation strategies are used over the default XRP Ledger topology and show that some augmentation strategies achieve robustness metrics equal to or exceeding the rewiring strategy, even when the number of edges added is small (e.g., three edges per node). Additionally, we show that the random K-out-based augmentation strategy maintains higher topological similarity to the original network than rewiring, as measured by Jaccard similarity.

0.20

Information-Theoretic Secure Aggregation With Heterogeneous Client Quantization

cs.IT cs.CRcs.LGcs.NI+1 ·2026-10-26 ·Shreya Meel, Sennur Ulukus, Itzhak Tamo
similarity 0.63
Abstract

In federated learning (FL), secure aggregation enables a server to compute the sum of local model updates of $N$ clients, without revealing any information on the individual model updates to the server, beyond their sum. Different clients may be subject to heterogeneous bandwidth constraints, and consequently may choose different numbers of quantization levels to represent the information they send. Most secure aggregation works require the clients to project the values of their update parameters to a common finite group (or field), which does not directly accommodate heterogeneous precision constraints on their transmitted masked updates. Existing approaches of secure aggregation with heterogeneous quantization levels reveal partial aggregates of model-updates, and can reveal segments of individual model updates, under certain dropout and client-server collusion patterns. To prevent this privacy breach, we propose an information-theoretic secure aggregation scheme that tolerates client drop-outs, and up to $T$ semi-honest clients that collude with each other and with the server, under heterogeneous quantization at clients. Our protocol utilizes the $(T+1, N)$ threshold black-box secret sharing construction, where secret shares of the client updates, despite belonging to distinct algebraic groups owing to different quantization, are generated from identical linear integer systems.

0.15

STAKE: Preventing a colluding majority from double spending

cs.GT ·2026-10-01 ·Zahra Naderi, Vincent Gramoli
similarity 0.63
Abstract

Blockchains typically operate in open networks where it is hard to control the delay of messages. While classic blockchain protocols assumed synchrony, newer protocols try to remain secure despite unexpected network delays. Unfortunately, in the traditional model where $n$ participants can either be honest or Byzantine, we need a supermajority, or $\lfloor 2n/3\rfloor + 1$, of them to be honest. Recent work have explored the question of reducing the number of needed honest nodes in a game theory model to a majority sometimes by introducing $k$ rational players and $t$ Byzantine players. Yet, to our knowledge, no blockchain protocol managed to reduce it further. In this paper, we offer a blockchain protocol called Secure and Tolerant Algorithm through ($k,t$)-robust Equilibrium (STAKE) that works with only $\lfloor n/3\rfloor + 1$ honest players. STAKE requires each consensus participant to stake a sufficiently large amount $s$ compared to their liquidity $\ell$. We show that the probability that a coalition manages to execute $ζ$ double spending attacks (we call them a $ζ$-uple attack) drops exponentially fast with $ζ$. This allows us to demonstrate that STAKE reaches a ($k,t$)-robust equilibrium, or that rational players do not collude with Byzantine, even with a relatively low $s/\ell$ ratio.

0.12

Projected Penalty-Gradient Tracking for Communication-Efficient Byzantine-Resilient Federated Learning

cs.LG cs.AI ·2026-11-17 ·Yanjie Dong
benchmark similarity 0.63
Abstract

We investigate communication-efficient federated learning over heterogeneous datasets in the presence of Byzantine adversaries capable of uploading arbitrary information. Penalty-based methods bound the influence of each worker through the bounded gradient of a penalty function; however, the bound is lost once the uploads are compressed, since a Byzantine worker can accumulate an unbounded state at the server. To retain the Byzantine resilience under compressed uploads, we propose a projected penalty-gradient tracking framework, where each honest worker uploads a compressed residual of its penalty gradient and the server projects each reconstructed state onto the known penalty-gradient ball. The framework accommodates any contractive compressor and yields two algorithms: fault-resilient proximal gradient with consistent sparsification (FRPG-CS), whose shared mask is protected by freshly drawn reserve rows, and lazily aggregated FRPG (LAG-FRPG), whose uploads are event-triggered. For smooth and strongly convex losses, we establish a finite-time bound on the expected objective gap, where the Byzantine error floor is independent of the compressor and the compression error decays faster than the optimization error. We also bound the expected number of lazy uploads and derive certificates that separate the finite-penalty model bias from the optimization error. Experiments on MNIST and Fashion-MNIST show that the proposed algorithms attain the highest accuracy among twelve methods under the Min-Max attack, whereas a compressed-momentum benchmark and a local-update benchmark remain preferable in attack-free accuracy and total traffic, respectively.

0.18

GUARDTs: Decentralized Access Control for Replicated Data Types

cs.PL cs.DC ·2026-11-05 ·Christian Kuessner, Ragnar Mogk, Julian Haas, Annette Bieniusa, Mira Mezini
similarity 0.62
Abstract · 24 pages, 10 figures

Replicated data types providing strong eventual consistency offer a principled foundation for developing decentralized software. Yet existing approaches to programming such data types leave access control unresolved: they either provide none at all, delegate it to a trusted coordinator, reintroducing the centralization they were designed to avoid, or tie it to specific data-type constructions, while typically assuming non-Byzantine replicas and static policies. We present GUARDTs: Guarded Unforgeable Algebraic Replicated Data Types, which embed fine-grained permissions directly into the application data model, operate without a central authority, support dynamic policy evolution, and tolerate Byzantine replicas. We formally prove that GUARDTs guarantee confidentiality, integrity, and availability and show empirically that their access control adds negligible overhead on top of the cost of Byzantine-resilient replication itself.

0.29

On the Robustness of Gossip Protocols in Modern Blockchains

cs.CR ·2026-10-15 ·Wenting Li, Jannik Albrecht, Frederik Armknecht, Ghassan Karame
top venue similarity 0.62
Abstract · Accepted at IEEE Symposium on Security and Privacy (IEEE SP), 2027

Modern platforms such as Ethereum and Polkadot nowadays execute Byzantine fault-tolerant consensus protocols over large validator committees, often comprising hundreds of nodes. At this scale, complete graph topologies for connecting nodes are impractical, leading systems to adopt various gossip mechanisms, often in an ad hoc manner. In this paper, we study the robustness of widely deployed gossip protocols used in committee-based blockchains against realistic network adversaries. We show, both analytically and through extensive empirical measurements, that the graph parameters commonly chosen to instantiate random graphs are insufficient to guarantee that enough honest nodes receive consensus messages for quorum formation in existing protocols. Motivated by this finding, we empirically assess the robustness of Bitcoin's Erdős-Rényi (ER) graphs, Polkadot's grid topology, Ethereum's GossipSub, and Solana's chunk- and tree-based disseminations. Our results reveal surprising tradeoffs: Solana's dynamic trees are bandwidth-efficient in benign settings but fragile under adaptive attacks; Polkadot's grid achieves strong robustness at the cost of high bandwidth overhead; GossipSub is both bandwidth-efficient and resilient to adaptive adversaries, yet highly sensitive to parameter choices; and ER graphs provide a strong robustness-efficiency tradeoff, e.g., when the (average) fanout degree exceeds 15 for networks up to 5000 nodes.

0.29