Role of feedback in modulo-sum computation over K-user erasure multiple-access channels

The modulo-sum computation of messages over a K-user finite-field erasure multiple access channel (MAC) is studied, with emphasis on the role of feedback in the large system regime. 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 where each transmitter uses the same linear code and the receiver leverages the additive structure of the multiple access channel to compute the modulo sum. 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, where the receiver first decodes messages of all users and then computes the modulo sum. This is in contrast to the two-user case where the currently best known achievability, reported by Khisti, Hern, and Narayanan in 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 Ω(1/log(K)), much higher than the scaling Θ(1/K) achieved by the grouping scheme without feedback. Our result hints at significant gain in function computation due to feedback in the large system regime when the transmitters are connected intermittently to the receiver, in sharp contrast to the static case where feedback provides no gain at all.