Universal Feedback Gain for Modulo-Sum Computation Over the Erasure MAC

The problem of computing the modulo-sum of independent messages over a finite-field erasure multiple access channel is investigated. The focus is on the role of delayed state feedback for function computation over state dependent multiple access channels. For the two-user case, a set of new outer bounds on the non-feedback computation capacity region are developed, which strictly improve the state of the art by Khisti et al. , 2013. As a result, a previously unsettled question is answered in the affirmative: delayed state feedback strictly increases computation capacity for the two-user erasure multiple access channel universally. The proof leverages the subset entropy inequalities by Madiman and Tetali, 2010, Jiang et al. , 2014, and submodularity of conditional entropies. For the achievability part of the non-feedback case, an achievable computation rate region is derived by generalizing the proposed schemes in Khisti et al. , 2013. Beyond the two-user case, the $K$ -user case is also investigated, with emphasis on the large system regime, where $K$ is the number of users. For the non-feedback case, we propose a grouping scheme which has higher computation rate than that of the conventional “compute-and-forward” ( CF ) scheme. Furthermore, with a growing number of users, the proposed grouping scheme strictly outperforms the conventional “decode-and-forward ( DF )” scheme when the erasure probability is smaller than $1-e^{\frac {1}{e}}\approx 0.3078$ . This is in contrast to the two-user case where the currently best known achievability (Khisti et al. , 2013) coincides with the better one between DF and CF . For the case with delayed state feedback, a new hybrid-ARQ-type scheme is proposed, and in the large system regime, it achieves a computation rate scaling like $\Omega \left({\frac {1}{\log (K)}}\right)$ , much higher than the scaling $\Theta \left({\frac {1}{K}}\right)$ achieved by the grouping scheme without feedback.