Information flooding

This paper studies the problem of broadcasting a common message over a relay network as the canonical platform to investigate the utilities and limitations of traditional relay coding schemes. For a few special classes of networks, such as the-S node relay channel and the-4 node diamond network, the decode-forward coding scheme by Cover and El Gamal, and its generalization to networks by Xie and Kumar, and Kramer, Gastpar, and Gupta achieve the cutset bound, establishing the capacity. When the network has cycles, however, decode-forward is suboptimal in general and is outperformed by partial decode- forward, compress-forward, or more generally, interactive relaying built upon these *-forward coding schemes. In particular, it is demonstrated via a simple example that a coding scheme based on interactive computing by Orlitsky and Roche, and its infinite-round generalization by Ma and Ishwar can strictly outperform existing noninteractive or finite-round interactive coding schemes. Roughly speaking, when the network is to be flooded with information, it is more efficient for the relays to spray tiny droplets of the information back and forth than to splash a huge amount at a time.