Feedback Increases the Capacity of Queues With Bounded Service Times

In the classical "Bits Through Queues" paper, it was hypothesized that full feedback always increases the capacity of first-in-first-out queues, except when the service time distribution is memoryless. More recently, a non-explicit sufficient condition under which feedback increases capaci...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2024-10, Vol.70 (10), p.6823-6833
Main Authors: Sahasranand, K. R., Tchamkerten, Aslan
Format: Article
Language:English
Subjects:
Decoding
Entropy
feedback
KKT conditions
memoryless
Queue channels
Random variables
Servers
service time distribution
Timing
Transmitters
Upper bound
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the classical "Bits Through Queues" paper, it was hypothesized that full feedback always increases the capacity of first-in-first-out queues, except when the service time distribution is memoryless. More recently, a non-explicit sufficient condition under which feedback increases capacity was provided, along with simple examples of service times meeting this condition. While this condition yields examples where feedback is beneficial, it does not offer explicit structural properties of such service times. In this paper, we show that full feedback increases capacity whenever the service time has bounded support. This is achieved by investigating a generalized notion of feedback, with full feedback and weak feedback as particular cases.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2024.3421909