The Information Flow Problem on Clock Networks

Abstract

The information flow problem on a network asks whether $r$ senders, $v_1,v_2,\dots ,v_r$ can each send messages to $r$ corresponding receivers $v_{n+1},\dots ,v_{n+r}$ via intermediate nodes $v_{r+1},\dots ,v_n$. For a given finite $R\subset {\mathbb{Z}}^{+}$, the clock network $N_n(R)$ has edge $v_i{v}_k$ if and only if $k>r$ and $k-i\in R$. We show that the information flow problem on $N_n(\{1,2,\dots ,r\})$ can be solved for all $n\ge r$. We also show that for any finite $R$ such that $\gcd (R)=1$ and $r=\max (R)$, we show that the information flow problem can be solved on $N_n(R)$ for all $n\ge 3r^3$.

11 pages

References in corpus (1)

• Broadcasting with side information