Computation in multicast networks: Function alignment and converse theorems
Changho Suh, Naveen Goela, Michael Gastpar · 2012
We characterize the computing capacity of a two-transmitter two-receiver linear deterministic network where both receivers wish to compute a modulo-2 sum of two Bernoulli sources generated at the two transmitters. We develop a new achievable scheme that we call function alignment, inspired by the concept of interference alignment, and derive a new upper bound to establish the computing capacity. As a consequence, we find that unlike the single-receiver function-unicasting case, the cutset-based bound is not tight in general when multicasting a linear function. Moreover we develop a network decomposition theorem to find elementary subnetworks that can constitute an original network without loss of optimality. This serves to provide a conceptually-simpler achievability proof as well as generalize to L-transmitter L-receiver networks.