Title: Probabilistic Forwarding of Coded Packets on Networks,
Abstract: We consider a scenario of broadcasting information over a network of nodes
connected by noiseless communication links. A source node in the network has
$k$ data packets to broadcast, and it suffices that a large fraction of the
network nodes receives the broadcast. The source encodes the $k$ data packets
into $n \ge k$ coded packets using a maximum distance separable (MDS) code, and
transmits them to its one-hop neighbours. Every other node in the network
follows a probabilistic forwarding protocol, in which it forwards a previously
unreceived packet to all its neighbours with a certain probability $p$. A
"near-broadcast" is when the expected fraction of nodes that receive at least
$k$ of the $n$ coded packets is close to $1$. The forwarding probability $p$ is
chosen so as to minimize the expected total number of transmissions needed for
a near-broadcast. In this paper, we analyze the probabilistic forwarding of
coded packets on two specific network topologies: binary trees and square
grids. For trees, our analysis shows that for fixed $k$, the expected total
number of transmissions increases with $n$. On the other hand, on grids, we use
ideas from percolation theory to show that a judicious choice of $n$ will
significantly reduce the expected total number of transmissions needed for a
near-broadcast.