In their seminal 1996 paper, Anantharam and Verdú showed that feedback does not increase the capacity of a queue under First-in-First-Out service policy and exponentially distributed service time. Since the channel has memory, this negative result raises the question whether it extends to other non-trivial combinations of service policy and service time. This paper addresses this question by providing two sufficient conditions under which feedback either increases capacity or does not increase capacity. The first is a sufficient condition on the service time distribution for feedback to increase capacity under First-In-First-Out service policy. The second is a sufficient condition for feedback not to increase capacity and is general in that it depends on the output distribution of the queue, but explicitly depends neither on the queue policy nor on the service time distribution. This condition is satisfied, for instance, by queues with Last-Come-First-Serve service policy and bounded service times.

In their “Bits Through Queues” paper, Anantharam and Verdu showed that, under FIFO service policy, feedback does not increase the capacity of a queue when the service time is exponentially distributed. Whether this negative and surprising result-since the channel has memory-holds for other combinations of service policies and service times ever since has remained an open question. This paper first provides a sufficient condition on the service time distribution for feedback to increase capacity under First-In-First-Out service policy. Underlying this condition is a notion of weak feedback wherein instead of the queue departure times the transmitter is informed about the instants when packets start to be served. Service times that satisfy this condition include a uniformly distributed service time for the continuous-time model and a binary service time for the discrete-time model. Second, a sufficient condition is given under which feedback does not increase capacity. This condition is satisfied, for instance, by queues with Last-Come- First-Served service policies and bounded service times.