Capacity of systems with queue-length dependent service quality

We study the information-theoretic limit of reliable information processing by a server with queue-length dependent quality of service. We define the capacity for such a system as the number of bits reliably processed per unit time, and characterize it in terms of queuing system parameters. We also characterize the distributions of the arrival and service processes that maximize and minimize the capacity of such systems, observing a minimum around the memoryless distribution. The problem is theoretically motivated by an effort to incorporate the notion of reliability in queueing systems, and is applicable in contexts of multimedia communication, crowdsourcing, and stream computing.

• Publication year

  2016

• Venue

  International Symposium on Information Theory and its Applications

• Publication date

  2016-03-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1603.01675
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Queuing Systems

  2018cited by this paper
• Capacity of Systems with Queue-Length Dependent Service Quality

  2017cited by this paper
• Queuing Models for Abstracting Interactions in Bacterial Communities

  2015cited by this paper
• Improving Impact Sourcing via Efficient Global Service Delivery

  2015cited by this paper
• Work capacity of freelance markets: Fundamental limits and decentralized schemes

  2015cited by this paper
• The Ignorant Led by the Blind: A Hybrid Human–Machine Vision System for Fine-Grained Categorization

  2014cited by this paper
• Reliable Crowdsourcing for Multi-Class Labeling Using Coding Theory

  2013cited by this paper
• Bits through bufferless queues

  2013cited by this paper
• Characterizing the Efficacy of the NRL Network Pump in Mitigating Covert Timing Channels

  2012cited by this paper
• Information theoretic analysis of side channel information leakage in FCFS schedulers

  2011cited by this paper
• On the transmission of bursty sources

  2006cited by this paper
• Zero-rate reliability of the exponential-server timing channel

  2005cited by this paper
• A universal approach to queuing with distortion control

  2005cited by this paper
• Elements of Information Theory

  2005cited by this paper
• Job Scheduling and Multiple Access

  2003cited by this paper
• Information-Spectrum Methods in Information Theory

  2002cited by this paper
• An information-theoretic and game-theoretic study of timing channels

  2002cited by this paper
• Multiple description coding: compression meets the network

  2001cited by this paper
• Entropy and the timing capacity of discrete queues

  2001cited by this paper
• Sequential decoding for the exponential server timing channel

  2000cited by this paper
• On the capacity of some channels with channel state information

  1998cited by this paper
• Information Theory and Communication Networks: An Unconsummated Union

  1998cited by this paper
• The Information-Theoretic Capacity of Discrete-Time Queues

  1997cited by this paper
• Combining Queueing Theory with Information Theory for Multiaccess

  1995cited by this paper
• A general formula for channel capacity

  1994cited by this paper
• Bits through queues

  1994cited by this paper
• Multi-access communications with decision feedback decoding

  1992influential reference
• Traffic smoothing effects of bit dropping in a packet voice multiplexer

  1988cited by this paper
• Queues, Priorities, and Social Process

  1978cited by this paper
• Queueing Systems: Volume I-Theory

  1975influential reference
• Queues with State-Dependent Stochastic Service Rates

  1967cited by this paper
• Information and information stability of random variables and processes

  1964cited by this paper
• Information and Information Stability of Random Variables and Processes

  1964cited by this paper

• Polar Codes Achieve Classical Capacity for Erasure and Unital Markovian Quantum Channels

  2025cites this paper
• Capacity Achieving Channel Codes for an Erasure Queue-Channel

  2024cites this paper
• Capacity Achieving Codes for an Erasure Queue-channel

  2023cites this paper
• An Erasure Queue-Channel with Feedback: Optimal Transmission Control to Maximize Capacity

  2023cites this paper
• Towards Maximizing Nonlinear Delay-Sensitive Rewards in Queuing Systems

  2022influential citation
• The Classical Capacity of Quantum Jackson Networks with Waiting Time-Dependent Erasures

  2022cites this paper
• Unital Qubit Queue-Channels: Classical Capacity and Product Decoding

  2021influential citation
• Queue-Channel Capacities with Generalized Amplitude Damping

  2021cites this paper
• Exploring the Relationship between Aviation Service Quality and Customer Satisfaction Based on Big Data Technology

  2020cites this paper
• The Classical Capacity of Additive Quantum Queue-Channels

  2020cites this paper
• Channels, Learning, Queueing and Remote Estimation Systems With A Utilization-Dependent Component

  2019cites this paper
• On Multiple-Access in Queue-Length Sensitive Systems

  2019influential citation
• The Classical Capacity of a Quantum Erasure Queue-Channel

  2019cites this paper
• On Multiple-Access Systems with Queue-Length Dependent Service Quality

  2019cites this paper
• Qubits through Queues: The Capacity of Channels with Waiting Time Dependent Errors

  2018cites this paper
• Scheduling a Human Channel

  2018cites this paper
• On Multiuser Systems with Queue-Length Dependent Service Quality

  2018cites this paper
• Capacity of Systems with Queue-Length Dependent Service Quality

  2017cites this paper
• The Role of Information Theory and Queuing Theory in Human Computation Systems

  2016cites this paper