On the Information Velocity over a Tandem of Erasure Channels
This work advances the theoretical understanding of information velocity in multi-hop networks, providing tight bounds for specific regimes, though the results are incremental and domain-specific.
The paper characterizes the optimal information velocity for a tandem of erasure channels when the message size grows slower than the square root of the number of hops, achieving reliable communication with a simple bit-separation scheme. For larger message sizes, with global state information, the optimal velocity is characterized for message size up to o(k).
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.