pith. sign in

arxiv: 2604.13588 · v1 · submitted 2026-04-15 · 💻 cs.IT · math.IT

On the Information Velocity over a Tandem of Erasure Channels

Kai-Chun Chen , I-Hsiang Wang This is my paper

Pith reviewed 2026-05-10 12:38 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords information velocitytandem erasure channelsbinary erasure channelpipeliningglobal state informationasymptotic analysisnetwork information theory
0
0 comments X

The pith

A simple bit-separation scheme achieves the optimal information velocity for messages of size o(k to the 1/2) over tandem binary erasure channels without feedback.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks to determine the highest speed at which reliable multi-bit messages can propagate end-to-end across a growing chain of erasure channels. It establishes this speed for messages that grow slower than the square root of the number of hops by showing that bits can be sent in a spaced-out sequence so their paths rarely overlap. This matters because it replaces earlier complex coding methods with a straightforward pipelining approach that still meets the fundamental limit. The work further shows that providing every node with global channel state information extends the characterization to larger messages up to linear size in the number of hops, yet supplies no extra benefit when messages remain smaller than the square root scaling.

Core claim

We characterize the optimal IV for the regime where the message size m = o(k^{1/2})... we develop an enhanced scheme and characterize the optimal IV for the regime where the message size m = o(k). Interestingly, for the regime m = o(k^{1/2}), GSI does not improve the information velocity.

What carries the argument

The bit-separation scheme that pipelines message bits in an orderly fashion with carefully designed temporal spacing so that the flows of different bits do not collide with one another with high probability.

If this is right

  • Complex coding across time and nodes is unnecessary to achieve optimal velocity when messages are sufficiently small.
  • Global state information permits characterization of optimal velocity up to message sizes linear in the number of hops.
  • The information velocity remains the same with or without global state information in the regime m = o(k^{1/2}).
  • Simple temporal spacing suffices to prevent collisions with high probability in long tandem networks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The spacing technique could extend to other memoryless channels where collision probability can be bounded by timing alone.
  • The gap between the o(sqrt(k)) and o(k) regimes without global state information remains open for future characterization.
  • Low-complexity pipelining may prove useful in resource-constrained relay networks where coding overhead must be minimized.

Load-bearing premise

The results hold only in the asymptotic regime where the number of hops tends to infinity while the message size scales as o(k to the 1/2) without feedback or o(k) with global state information and the error probability vanishes.

What would settle it

If simulations or analysis for a sequence of large k with m scaling as k to the power 0.4 show that the error probability of the bit-separation scheme stays bounded away from zero, the claimed optimality would be refuted.

Figures

Figures reproduced from arXiv: 2604.13588 by I-Hsiang Wang, Kai-Chun Chen.

Figure 1
Figure 1. Figure 1: A tandem network of BEC links We also revisit the scheme of [5] and point out that it seems necessary for each node in the tandem network to have strictly causal access to not only the state information of the succeeding hop (feedback) and the preceding hop, but also that of all the other preceding hops in the entire network. Under such an assumption that global state information (GSI) is available, the ac… view at source ↗
Figure 2
Figure 2. Figure 2: Information velocity (log scale) vs. erasure probability. “Inovan’s” refers to [6], and “Ling & Scarlett’s” refers to [4]. [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
read the original abstract

Information velocity (IV) is a recently proposed notion to capture the speed of reliable information dissemination over a large-scale network. It is the speed at which reliable end-to-end communication over $k$ hops can be achieved within $t$ time instances, and is defined formally as the asymptotic ratio $k/t$ as $k$ tends to infinity subject to vanishing error probability. To date, even for a tandem of binary erasure channels without feedback, the optimal IV for disseminating multiple (say $m$) bits remains unknown. We make progress on this open problem by characterizing the optimal IV for the regime where the message size $m = o(k^{1/2})$. The main contribution lies in achievability, where we propose a simple bit-separation scheme that pipelines message bits in an orderly fashion with carefully designed temporal spacing so that the flows of different bits do not collide with one another with high probability. This is in sharp contrast to previous attempts in the literature where schemes involve coding over time and across nodes. To go beyond the regime $m = o(k^{1/2})$, we further investigate the setting where every node in the network has strictly causal access to the state information of the BEC links in the entire network. For such a setting with global state information (GSI), we develop an enhanced scheme and characterize the optimal IV for the regime where the message size $m = o(k)$. Interestingly, for the regime $m = o(k^{1/2})$, GSI does not improve the information velocity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to characterize the optimal information velocity (IV) for disseminating m bits over a tandem of k binary erasure channels (BECs) in the asymptotic regime k → ∞ with vanishing error probability. For the regime m = o(k^{1/2}) without feedback, a bit-separation achievability scheme is proposed that pipelines message bits with carefully designed temporal spacing to ensure different bit flows do not collide with high probability. With global state information (GSI) available at every node, an enhanced scheme is developed to characterize the optimal IV for the larger regime m = o(k). The paper also observes that GSI yields no improvement to the IV in the m = o(k^{1/2}) regime.

Significance. If the characterizations hold, this work makes concrete progress on an open problem in network information theory by providing the first explicit optimal IV expressions under these message-size scalings. The bit-separation construction is a strength: it is simple, avoids coding across time and nodes, and relies on pipelining with spacing to control collisions. The observation that GSI provides no benefit for m = o(k^{1/2}) is interesting and suggests limits on the value of state information at small scales. These results, if rigorously supported by matching achievability and converse arguments, could serve as a baseline for studying reliable dissemination in larger networks.

major comments (2)
  1. [Achievability scheme] The bit-separation scheme (described in the achievability section): the temporal spacing parameter must be chosen so that the probability of any two bit flows colliding vanishes as k → ∞ under m = o(k^{1/2}); the high-level description does not explicitly derive the scaling of this spacing or the resulting collision probability bound, which is load-bearing for claiming optimality.
  2. [GSI comparison] The claim that GSI does not improve IV for m = o(k^{1/2}): this requires a converse bound that remains unchanged even when global state information is available; if the upper bound is derived only for the no-feedback case, it must be shown that additional state information cannot increase the IV in this regime, which is central to the interesting observation.
minor comments (2)
  1. [GSI model] Clarify the precise definition of 'strictly causal' GSI access (past states only, or including current time slot) and how it affects the enhanced scheme for m = o(k).
  2. [Introduction] The abstract states the IV is the asymptotic ratio k/t; ensure this is formally restated with the vanishing-error condition in the introduction or preliminaries for reader clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback. We address each major comment below and will revise the manuscript accordingly to enhance clarity and rigor.

read point-by-point responses

  1. Referee: [Achievability scheme] The bit-separation scheme (described in the achievability section): the temporal spacing parameter must be chosen so that the probability of any two bit flows colliding vanishes as k → ∞ under m = o(k^{1/2}); the high-level description does not explicitly derive the scaling of this spacing or the resulting collision probability bound, which is load-bearing for claiming optimality.

    Authors: We agree that an explicit derivation of the spacing and collision bound is essential for rigor. In the revised manuscript, we will expand the achievability analysis to specify the temporal spacing scaling (chosen proportionally to log k to separate flows) and provide a detailed union-bound calculation over all bit pairs. This will show that the probability of any collision vanishes as k → ∞ whenever m = o(k^{1/2}), thereby supporting the optimality claim. revision: yes

  2. Referee: [GSI comparison] The claim that GSI does not improve IV for m = o(k^{1/2}): this requires a converse bound that remains unchanged even when global state information is available; if the upper bound is derived only for the no-feedback case, it must be shown that additional state information cannot increase the IV in this regime, which is central to the interesting observation.

    Authors: We acknowledge the need to confirm the converse applies under GSI. Our upper bound is derived from the tandem structure and erasure statistics, without relying on the absence of state information. We will add a clarifying remark in the revised version stating that the same bound holds with GSI, as any additional state knowledge cannot overcome the fundamental hop-by-hop erasure limitations in this small-message regime. Since the bit-separation scheme achieves the bound without GSI, this establishes that GSI yields no improvement. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper defines IV as the asymptotic k/t ratio under vanishing error as k→∞. Achievability for m=o(k^{1/2}) rests on an explicit bit-separation scheme that pipelines bits with designed temporal spacing to avoid collisions with high probability; the enhanced scheme with GSI extends this for m=o(k). The characterization is completed by a matching converse that holds independently of state information in the smaller-m regime. No equation or claim reduces the optimal IV expression to a fitted parameter, self-referential definition, or load-bearing self-citation chain; the central result follows from the construction and standard asymptotic analysis rather than from renaming or smuggling prior ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard definitions of binary erasure channels, asymptotic limits, and vanishing error probability from classical information theory; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard properties of binary erasure channels and the definition of information velocity as lim k/t with vanishing error as k to infinity
    The IV definition and channel model are invoked directly from prior literature without additional justification in the abstract.

pith-pipeline@v0.9.0 · 5574 in / 1247 out tokens · 36395 ms · 2026-05-10T12:38:12.205165+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

  1. [1]

    A. E. Gamal and Y .-H. Kim,Newtork Information Theory. Cambridge University Press, 2011

    work page 2011

  2. [2]

    Relaying one bit across a tandem of binary-symmetric channels,

    W. Huleihel, Y . Polyanskiy, and O. Shayevitz, “Relaying one bit across a tandem of binary-symmetric channels,” in2019 IEEE International Symposium on Information Theory (ISIT), 2019, pp. 2928–2932

    work page 2019

  3. [3]

    A coding theorem for distributed computation,

    S. Rajagopalan and L. Schulman, “A coding theorem for distributed computation,” inProceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, ser. STOC ’94. New York, NY , USA: Association for Computing Machinery, 1994, pp. 790–799. [Online]. Available: https://doi.org/10.1145/195058.195462

    work page doi:10.1145/195058.195462 1994

  4. [4]

    Simple coding techniques for many-hop relaying,

    Y . H. Ling and J. Scarlett, “Simple coding techniques for many-hop relaying,”IEEE Transactions on Information Theory, vol. 68, no. 11, pp. 7043–7053, 2022

    work page 2022

  5. [5]

    The information velocity of packet-erasure links,

    E. Domanovitz, T. Philosof, and A. Khina, “The information velocity of packet-erasure links,” inIEEE INFOCOM 2022 - IEEE Conference on Computer Communications, no. 190-199, 2022

    work page 2022

  6. [6]

    On speed and advantage: Results in information velocity and monitoring problems,

    R. Inovan, “On speed and advantage: Results in information velocity and monitoring problems,” Ph.D. dissertation, EPFL, Lausanne,

    work page

  7. [7]

    Available: https://infoscience.epfl.ch/handle/20.500.14299/207871 April 16, 2026 DRAFT 11

    [Online]. Available: https://infoscience.epfl.ch/handle/20.500.14299/207871 April 16, 2026 DRAFT 11

    work page 2026

  8. [8]

    Information velocity of cascaded Gaussian channels with feedback,

    E. Domanovitz, A. Khina, T. Philosof, and Y . Kochman, “Information velocity of cascaded Gaussian channels with feedback,”IEEE Journal on Selected Areas in Information Theory, vol. 5, pp. 554–569, 2024

    work page 2024

  9. [9]

    Hydrodynamic scaling, convex duality, and asymptotic shapes of growth models,

    T. Seppäläinen, “Hydrodynamic scaling, convex duality, and asymptotic shapes of growth models,”Markov Processes and Related Fields, 01 1998

    work page 1998

  10. [10]

    Shape fluctuations and random matrices,

    K. Johansson, “Shape fluctuations and random matrices,”Communications in Mathematical Physics, vol. 209, no. 2, pp. 437–476, Feb. 2000. APPENDIXA PROOF OFPROPOSITION4.1 To make the argument in the sketch proof concrete, let us first derive the expected value ofI j,n, which can be computed by recursively invoking the law of total expectation: forj= 0,1, . ...

    work page 2000