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, Hern, and Narayanan [1]. 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 [2], Jiang, Marukala, and Liu [3], 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 [1]. 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 nonfeedback case, we propose a grouping scheme which has higher computation rate than that of the conventional “compute-andforward” (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 1/e ≈ 0.3078. This is in contrast to the two-user case where the currently best known achievability [1] 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 Ω(1/log(K)), much higher than the scaling Θ(1/K) achieved by the grouping scheme without feedback.