The Information Flow Problem on Clock Networks

The information flow problem on a network asks whether $r$ senders, $v_1,v_2, \ldots ,v_r$caneachsendmessagesto$r$correspondingreceivers$v_{n+1}, \ldots ,v_{n+r}$viaintermediatenodes$v_{r+1}, \ldots ,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$.