CS Paper Radar

Off-Tree Forwarding for Accelerating Broadcasts from Arbitrary Sources in Plumtree

Ryohei Banno

cs.DC cs.NI ·submitted 2026-10-18 09:59 UTC · v1

Abstract

Overlay broadcast is fundamental to large-scale distributed systems, enabling messages to be disseminated to all participants. Plumtree is a well-established protocol that embeds a spanning tree in a gossip overlay: payloads are disseminated along tree links, while non-tree links support recovery and optimization. However, because the tree is constructed from the first broadcast, it is optimized for the initial source and can introduce long detours for broadcasts originating at other nodes, particularly leaf nodes. To address this limitation, we propose probabilistic exuding, an off-tree forwarding mechanism in which nodes near the source additionally forward payloads over their non-tree links with a specified probability. Exuded messages use a dedicated message type and do not participate in tree construction or repair, leaving the shared tree unchanged. Simulations on a 1000-node random regular overlay show that, for randomly selected sources and a representative parameter setting, the proposed method reduces the 95th-percentile delivery latency by approximately 40% relative to Plumtree. This closes approximately 92% of the latency gap between Plumtree and flooding while sending only about 58% as many payload messages as flooding. In contrast, Plumtree's own link optimization and shorter repair timeouts, which also exploit non-tree links, rewire the shared tree and increase latency as broadcast sources change; the latency of exuding is nearly unaffected.

Closest papers

Nearest neighbours by meaning across the whole index.

eAVID: Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

cs.DC ·2026-08-16 ·Rithwik Kerur, Dahlia Malkhi, Michael K. Reiter
similarity 0.64
Abstract

The well-known Asynchronous Verifiable Information Dispersal (AVID) problem lets a sender disperse a message across $N=3F+1$ nodes such that it remains recoverable despite up to $F$ Byzantine failures and unbounded message delays. An optimal AVID scheme requires $3\times$ the message size in communication and storage: up to $F$ nodes may be delayed in responding, and among the remaining $2F+1$ respondents, up to $F$ may be Byzantine. This paper presents eAVID, an elastic AVID scheme that provides two key improvements. First, after dissemination, nodes can prune up to half of their stored information without requiring anyone to reconstruct or recode the message. Second, pruning is enabled by an extremely simple protocol. Nodes collect acknowledgments from one another confirming receipt of their coded pieces, after which each node locally prunes its stored information. eAVID achieves this $2\times$ reduction while making two tradeoffs: the sender generates $2N$ fragments rather than $N$, and pruning may necessitate contacting $2F+1$ nodes for message retrieval rather than $F+1$. eAVID was implemented in DispersedSimplex, a simple-to-understand BFT consensus protocol that erasure-codes its blocks. The implementation demonstrates two features. First, eAVID achieves these improvements using a flat erasure-coding scheme that requires no metadata or bookkeeping at the nodes during reconstruction. Second, it delivers the storage savings without a performance cost: with all nodes responsive, pruning fires on over $99\%$ of blocks and steady-state per-node storage falls by $42$-$46\%$ for committees of $10$ to $22$ nodes. Throughput and latency match the unmodified protocol showing that we can achieve these storage savings without any performance costs.

0.04

Attacking P2P Networks: Liveness Attacks on the GossipSub and DOG Gossip Protocols

cs.CR ·2026-11-02 ·Jiaheng Li, Anton Paramonov, Yann Vonlanthen
similarity 0.62
Abstract

Peer-to-peer (P2P) networks form the communication layer of large decentralized systems such as Ethereum, and the correctness of higher-level protocols depends on the gossip layer delivering messages to honest nodes. We study the robustness of two gossip protocols against adversaries whose only goal is to violate liveness, that is, to prevent honest nodes from receiving fresh messages, without forging, altering, or invalidating any message. For GossipSub, the publish-subscribe protocol used by Ethereum, we show that an adversary operating a constant number of geographically distributed nodes with a fixed latency advantage can take over the ``First Message Deliveries'' peer-scoring term and separate a constant fraction of nodes from the honest mesh. We analyze the attack under a geographical model, address the random-peer and outbound-connection mechanisms, and show that the separation can be maintained under realistic churn. For DOG, a transaction-dissemination protocol designed for CometBFT, we first give simple counterexamples in which route filtering disconnects the dissemination graph even without failures or Byzantine participants, and then present a practical attack that uses only a single physical node with a constant number of identities and legitimate actions to disable every forwarding route, separating the full network while allowing only direct publisher-to-neighbor delivery. We verify the attack in a simulated network and analyze its cost, assumptions, and possible mitigations.

0.11

Scaling the Lightning Network with Practical Set Reconciliation

cs.NI ·2026-08-16 ·Xingyu Chen, Anish Sinha, David Starobinski, Ari Trachtenberg
published similarity 0.60
Abstract · Published in the 2026 IEEE International Conference on Blockchain and Cryptocurrency (ICBC 2026)

The Lightning Network (LN) utilizes gossip to share network topology, channel announcements and updates, and node announcements among its local constituents. Yet, our measurements show that this flooding-based gossip reconciliation is fundamentally inefficient. We propose, instead, to use set reconciliation protocols for sharing this information, and we systematically evaluate existing approaches under realistic network conditions. We further propose ADAPTIVEIBLT, a novel adaptive IBLT (Invertible Bloom Lookup Table) protocol with a partial-decoding enhancement. By simulating reconciliation in Core-Lightning and evaluating real gossip snapshots, we demonstrate the practical benefits of reconciliation in scaling gossip reconciliation from hours down to a few minutes.

0.28

Evict Early, Decode Efficiently: Lightweight Decoding Strategies for Low-Delay Sliding Window RLNC

cs.NI ·2026-10-20 ·Foteini Karetsi, Evangelos Papapetrou
similarity 0.57
Abstract · 14 pages, 7 figures

Random Linear Network Coding (RLNC), and in particular Sliding Window RLNC (SW-RLNC), is a promising approach for reliable, low-latency communication in dynamic environments such as 6G and non-terrestrial networks. While prior work has largely focused on encoder-side parameter tuning, such as the code rate and coding window size, decoder-side design remains comparatively underexplored despite its direct impact on end-to-end performance. This paper addresses decoding window management, namely the policies governing window-boundary updates, removal of obsolete packets, and delivery of recovered packets to upper layers, and shows that these policies critically shape the trade-off between computational complexity and decoding performance, particularly in-order delivery delay. We derive sufficient conditions under which packets can be safely removed from the decoding window without compromising decodability or violating in-order delivery guarantees, and, building on these conditions, propose two lightweight decoding window management schemes. Through extensive simulation-based evaluation across a range of channel conditions and code rates, we show that both schemes preserve decoding efficiency while substantially reducing decoding complexity, and that one additionally achieves a marked reduction in in-order delivery delay. These results establish decoding window management as a key design dimension for practical SW-RLNC systems.

0.27

EDAP: An Efficient Data-Gathering Protocol for Wireless Sensor Networks

cs.NI ·2026-10-02 ·Arash Nasiri Eghbali, Nastooh Taheri Javan, Mehdi Dehghan
publishedhighly cited similarity 0.56
Abstract

Directed Diffusion (DD), uses mechanisms such as data aggregation and in-network processing to suppress the additional data overhead however there is no guarantee that paths from nearby sources join after a few hops. Also for path construction, each source floods a distinct exploratory data (ED) packet through the network which is not necessary for nearby sources. In this paper an efficient data-gathering protocol (EDAP) is proposed to address the problems of late-aggregation and distinct ED-flooding through using a virtual sink (VS) node nearby the sources which plays the role of sink node and broadcasts local interest messages and routed gathered data toward destination. Also in this protocol, multiple paths are constructed between virtual sink and the sink node which leads to load-balancing and increase in the life-time of the network nodes. Our routing protocol can produce more than one disjoint or braided path and spread the gathered data properly between constructed paths according to their length and remaining energy. Simulation results shows that in this way a significant amount of energy can be saved and the network lifetime will be increased considerably (up to 75% better than DD).

0.60

Byzantine Causal Reliable Broadcast with Constant Metadata Overhead

cs.DC cs.DS ·2026-09-29 ·Purv Patel, Ajay D. Kshemkalyani
similarity 0.56
Abstract

Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees. Causal message ordering is important for many applications such as blockchain and social networking. Existing solutions for Byzantine Causal Reliable Broadcast (BCRB) have several drawbacks. Such protocols typically append vector clocks or dependency barriers to application messages, resulting in a metadata overhead that scales linearly with $n$, the number of processes in the system. In this paper, we propose the first optimal message overhead BCRB algorithm that guarantees safety. We do this by re-engineering Bracha's BRB algorithm with relatively small but critical modifications, and prove that our algorithm solves BCRB with optimal message metadata. The algorithm achieves constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ messages, resulting in $\mathcal{O}(n^2)$ communication word complexity. This is as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols. The algorithm tolerates $f < n/3$ Byzantine processes, which is the well-known optimal resilience bound, and uses four phases.

0.34

SPICE: Sparse Parameter Gossip for LLM Pretraining

cs.DC ·2026-11-17 ·Pietro Cagnasso, Daniele Kopyshevskiy, Edouard Oyallon, Eugene Belilovsky
similarity 0.54
Abstract · Technical report, 19 pages, 7 figures, 7 tables

Pretraining language models across geographically distributed resources requires communication-efficient methods that operate under limited and variable internet bandwidth. Decentralized training replaces global collectives with peer exchanges, but full-model messages make larger peer neighborhoods costly. We introduce SPICE, which combines sparse parameter gossip with error feedback through corrected parameter values that remain directly interpretable as peer neighborhoods change. These sparse exchanges make broader neighborhoods affordable, achieving better training quality with less communication than the evaluated dense decentralized baselines. As the replica count grows, SPICEincreases the number of peers contacted while keeping individual messages sparse, limiting the quality degradation observed with dense gossip. Under bandwidth constraints, SPICE achieves higher training throughput than DDP and dense gossip, while sustaining throughput during transient link slowdowns.

0.28

Configuration-Induced Delivery Failures in NATS JetStream: Detection and Remediation

cs.NI ·2026-09-28 ·Biplab Kumar Das
code/data similarity 0.54
Abstract · 8 pages, 8 figures, 5 tables

NATS JetStream's at-least-once delivery guarantee is conditional: five common configuration mistakes silently violate it, causing duplicate message processing, data loss, or redelivery storms with no error logged anywhere. The standard Prometheus NATS exporter exposes only server-level throughput metrics and cannot detect any of these failures. We present nats-lens, a standalone monitor that reads from the JetStream management API and detects all five violation classes without requiring changes to monitored applications or client code. We formally characterize each class with a precise condition, prove that standard Prometheus NATS metrics are structurally incapable of detecting any of them, and implement five targeted detectors. In a controlled evaluation of 30 rounds per scenario on both single-node and 3-node JetStream clusters, nats-lens achieves 100% detection coverage across all five classes---versus 0% for the baseline---with zero false positives over 30 minutes of healthy operation. Detection latency ranges from 2,003 ms to 8,013 ms (within three poll cycles). We confirm language-agnostic detection empirically using consumers in Rust, Go, and Python. The tool is open source and exposes findings through four output channels: web dashboard, Prometheus metrics, REST API, and NATS health events.

0.39