CS Paper Radar

Concurrent Coded Signal-Multiplexing Ranging for Half-Duplex Asynchronous Networks

Zijian Zhang, Yuan Shen

cs.IT cs.IReess.SPeess.SY ·submitted 2026-09-27 16:52 UTC · v1

Abstract

Signal-multiplexing network ranging (SM-NR) shares broadcasts across node pairs, but its sequential operation leads to a ranging cycle that grows linearly with network size. This paper proposes a concurrent coded SM-NR (CC-SM-NR) framework for asynchronous half-duplex networks. Firstly, the CC-SM-NR protocol coordinates concurrent transmissions through binary transmit-listen codewords. The transmit-listen schedule defined by these codewords ensures reciprocal observations subject to a finite concurrency limit. Then, we derive the exact minimum number of transmit-listen rounds without a concurrency limit, which reveals that the minimum grows logarithmically with network size. To account for practical scenarios, we establish the necessary and sufficient conditions for the constant-weight feasibility of codewords under a finite concurrency limit. Subsequently, we propose a low-complexity scheduling algorithm that achieves the minimum round count within the constant-weight codeword class. To support higher observation redundancy, this scheduling design is extended through a greedy construction. Finally, simulation results demonstrate the effectiveness of the proposed schemes for network ranging.

Comment
15 pages, 11 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Task-Oriented Network Ranging via Joint Graph and Schedule Design

eess.SP cs.IRcs.ITcs.NI+1 ·2026-11-18 ·Zijian Zhang, Yuan Shen
similarity 0.65
Abstract · 16 pages, 14 figures, with appendices

Measuring inter-node distances is the basis for network localization, whereas acquiring node positions does not require a fully connected graph of distances. Existing complete-ranging protocols for network localization require every node pair to exchange signals, which prolongs the ranging cycle. In this paper, we propose sparse signal-multiplexing network ranging (S-SM-NR), a task-oriented framework that adapts the transmit-listen schedule to the ranging task required by network localization. First, we establish the S-SM-NR framework by formulating the joint design of the task graph and the transmit-listen schedule. Then, we analyze the minimum round count required by S-SM-NR and establish a connectivity condition for network localization. Subsequently, we develop a closed-form joint design that constructs the sparse task graph and the balanced transmit-listen schedule. In particular, the joint design can achieve the minimum round count under the complete physical connectivity. Finally, simulations show that the proposed S-SM-NR scheme reduces the occupied-round count and improves the localization accuracy by shortening the ranging cycle.

0.26

Linear Network Coding for Sum All-Reduce over Ring Networks

cs.IT ·2026-11-16 ·Yi Chen, Zhuoqi Tu, Shenghao Yang
publishedtheory similarity 0.54
Abstract

Sum All-Reduce is a fundamental collective communication primitive in which each node holds a local vector and every node must recover the componentwise sum of all vectors. In distributed training, this operation is often implemented over a ring topology using a reduce--multicast scheme. We study sum All-Reduce on directed rings via linear network coding, which includes reduce--multicast as a special case. We give a necessary and sufficient feasibility condition in terms of the coding matrices. For a ring with $N\geq 3$ nodes and unit-capacity links, where each node holds a vector containing $K$ symbols, we prove that the number of time units $T$ required by any feasible linear code satisfies $T\ge\max\bigl\{K+N-2,\ \lceil\frac{2(N-1)}{N}K\rceil\bigr\}$, giving a rate $K/T$ of at most $N/(2(N-1))$. The bound is tight over every field. When $K\ge N$, an interleaved reduce--multicast code achieves the bound; when $K<N$ and $K$ divides $N$, a reduce--partial-multicast code does. When $K<N$ and $K$ does not divide $N$, no coordinate-wise code---in particular, no reduce--multicast code---achieves the bound, while an explicit linear network code does.

0.41

Deterministic Distributed Linearly Separable Computation via Nested Cyclic Codes

cs.IT ·2026-10-13 ·Anu Mathew, M. Nikhil Krishnan
similarity 0.54
Abstract · 13 pages, 1 figure

We study the $(K,N,S,M,K_c)$ distributed linearly separable computation (DLSC) setting, where a master employs $N$ workers with a per-worker computation load of $M$ to recover $K_c$ deterministic linear combinations of $K$ messages in the presence of up to $S$ stragglers. We propose a DLSC framework based on nested cyclic codes that achieves $M=\frac{K}{N}(S+K_c)$. For sufficiently large $K$, we establish the matching converse $M\geq\frac{K}{N}(S+K_c)$, proving the asymptotic computation load optimality of the proposed framework. By instantiating cyclic locally recoverable codes (LRCs) as base codes in the framework, the master can recover the desired $K_c$ linear combinations by contacting fewer than $N-S$ workers under many straggler scenarios. This essentially softens the straggler threshold without increasing the computation load or communication cost. Finally, we extend the construction to reduce the per-worker communication load by a factor of $m$, while achieving an asymptotically optimal computation load of $M=\frac{K}{N}(S+mK_c)$.

0.20

Second-Order Asymptotics for the Gaussian MAC on the Relative Interior of the Sum-Rate Face

cs.IT ·2026-09-16 ·Vincent Y. F. Tan
similarity 0.53
Abstract · 37 pages; 9 figures

We completely characterize the second-order coding rate region of the two-user Gaussian multiple-access channel at points in the relative interior of the sum-rate face, under maximal per-codeword power constraints. For any fixed average error probability $0 < \varepsilon < 1/2$, a nontrivial mixture of power splits reduces the sum-rate dispersion and strictly improves upon standard inner bounds based on a constant power split. Thus, a constant power split, although sufficient to attain the first-order capacity region, is insufficient for second-order optimality in this regime. Our achievability proof builds on the constant composition and coded time-sharing framework of Scarlett, Martinez, and Guillén i Fàbregas, with an optimization over admissible power splits. A matching second-order converse establishes the optimality of the resulting coded time-sharing strategy.

0.49

Orthogonal Code-Based Parallel Signaling for PLCA in Shared-Medium Ethernet

cs.NI ·2026-11-11 ·Mohamed Elattar, Ahmed Abdelkader, Zhe Lou, Georg Carle
unusual similarity 0.52
Abstract · 7 pages, 3 figures, 2 tables. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice…

Physical Layer Collision Avoidance (PLCA) enables collision-free channel access in shared-medium Ethernet by granting each node an exclusive transmission opportunity (TO) in a sequential, cyclic manner. This sequential, node-based access structure, however, is the root cause of PLCA's fundamental limitations, causing access latency to grow with network size and idle TOs to accumulate when traffic is sparse, a limitation inherited by existing PLCA extensions. To address this, we propose OC-PLCA, an orthogonal code-based parallel signaling mechanism for PLCA. Rather than signaling sequentially, all nodes with pending traffic transmit their unique Walsh-Hadamard code simultaneously to signal their intent to transmit. Since these codes are mutually orthogonal, each node independently identifies the complete set of active nodes, allowing the transmission cycle to include only active nodes and eliminating idle TOs entirely. We further investigate the impact of quantization on active node detection, and propose a grouping-based extension that preserves unambiguous detection for networks of an arbitrary number of nodes. Theoretical analysis shows that OC-PLCA reduces signaling overhead by 88% for an 8-node network, with the reduction growing as network size increases. Simulation results confirm significant reductions in observed access latency across a range of network loads and heterogeneous node activity.

0.33

Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks

cs.IT ·2026-10-07 ·Xindan Zhang, Baochun Li, Zongpeng Li
theoryhighly cited similarity 0.51
Abstract · 17 pages

Network coding lets the nodes of a network combine messages rather than merely forward them. In undirected networks, where the two directions of an edge share its capacity, Li and Li conjectured in 2004 that coding offers no advantage over fractional routing; the conjecture has been confirmed for many special classes but never settled in general. In this paper, we disprove it by constructing a finite connected simple undirected network with unit shared edge capacities, maximum degree three, and distinct leaf terminals, on which a binary linear block code achieves a common rate strictly above the maximum fractional routing rate. The construction turns a short completion-time code into a reversible circuit whose registers all carry independent messages, and a temporal metric on its wires yields the strict routing bound. The underlying integer-coefficient construction works over every finite field and every nontrivial finite abelian group; for deterministic fixed-schedule codes the common-rate supremum is one and the closure of the rate region is the unit cube. Amplifying the gap with a degree-preserving tensor construction and an even subdivision gives, for every $0<β<1$, an unbounded family of connected, simple, subcubic, bipartite networks with girth at least $n^β$ on which coding approaches rate one while routing is bounded by $K_β/(\log n)^c$, with one positive exponent $c$ independent of $β$. The finite counterexample and the family theorem are formalized in Lean.

0.64

Non-asymptotic Sphere-Packing Bounds for Finite-Blocklength Scalar Gaussian Multiple-Access and Broadcast Channels

cs.IT ·2026-11-03 ·Kaixuan Bao, Wei Xu, Xiaohu You
theory similarity 0.51
Abstract · 51 pages, 6 figures

This paper investigates non-asymptotic achievable rate regions of Gaussian multiple-access channels (MACs) and broadcast channels (BCs) in the finite-blocklength regime. By employing a proposed volume-uniform random coding (VURC) codebook that distributes codewords uniformly within an $n$-dimensional power sphere, together with successive interference cancellation (SIC) decoding, we derive a closed-form achievability bound, a scheme-specific lower bound on the average error probability, and a fourth-order asymptotic characterization. The proposed SIC achievability bound admits a simple and analytically interpretable closed-form expression, enabling direct performance evaluation without iterative computation. The structure of the proposed SIC asymptotic bound offers a highly extensible framework, allowing advances in single-user finite-blocklength theory to be systematically incorporated into the multiuser setting. Futhermore, to characterize the performance benefit of joint decoding, we further derive numerical and closed-form achievability bounds for the two-user Gaussian MAC under joint nearest-neighbor (JNN) decoding. Numerical results illustrate the performance differences among the proposed SIC and JNN bounds and existing benchmarks.

0.22

A Particle-Based Multiuser Communication with a Budget Limit

eess.SP ·2026-11-04 ·Shaojie Zhang, Ozgur B. Akan
similarity 0.51
Abstract · 13 pages, 3 figures

Multiuser networks can aggregate local observations through a shared receiver. In this paper, we study the particle budget required to recover the exact sum of binary inputs in a multiuser network. We show that, for the considered model, the minimum budget grows quadratically with the number of transmitters when the symbol duration and target error probability are fixed, even when the receiver observes all particle arrival times. Simultaneous on-off keying (OOK) achieves this quadratic scaling, while any slower budget growth makes the error probability approach one at a fixed symbol duration, regardless of the transmission and decoding scheme. We then examine how this particle requirement can be reduced by allowing longer symbol durations and more counting intervals. We develop a groupwise OOK counting (GOC) scheme with staggered group releases and sequential estimation of group input sums, accounting for delayed arrivals. Our bounds show that, when reception is based on interval counts, reducing the quadratic scaling requires both the symbol duration and the number of counting intervals to grow with network size. When both grow in proportion to network size, the minimum budget becomes proportional to the number of transmitters times its logarithm.

0.29