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

The problem of computing the modulo-sum of messages over a finite-field erasure multiple access channel (MAC) is studied, and the role of feedback for function computation is explored. Our main contribution is two-fold. First, a new outer bound on the non-feedback computation capacity is proved, which strictly improves the state of the art [1]. The new outer bound answers a previously unsettled question in the affirmative: delayed state feedback strictly increases computation capacity for the two-user erasure MAC universally. The proof leverages the subset entropy inequality by Madiman and Tetali [2]. Second, focusing on the family of linear coding schemes with hybrid-ARQ-type retransmissions, we develop the optimal computation rate with delayed state feedback. For the considered family of schemes, it is always sub-optimal to compute modulo-sum by decoding all messages first. This is in contrast to the nonfeedback case [1] where sometimes the aforementioned “decode-all” strategy can reach the best known achievable rates.