Adversarial queuing theory

DOI10.1145/363647.363659zbMath1320.68053OpenAlexW2168550848WikidataQ57904556 ScholiaQ57904556MaRDI QIDQ2947002

Prabhakar Raghavan, Allan Borodin, David P. Williamson, Madhu Sudan, Jon M. Kleinberg

Publication date: 20 September 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/363647.363659

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (45)

Maria Serna's contributions to adversarial queuing theory ⋮ Packet latency of deterministic broadcasting in adversarial multiple access channels ⋮ Learning lexicographic orders ⋮ Robust Queueing Theory ⋮ Stable routing scheduling algorithms in multi-hop wireless networks ⋮ Maximum throughput of multiple access channels in adversarial environments ⋮ Tight performance bounds in the worst-case analysis of feed-forward networks ⋮ Stability in Heterogeneous Dynamic Multimedia Networks ⋮ The complexity of deciding stability under FFS in the adversarial queueing model ⋮ The network as a storage device: dynamic routing with bounded buffers ⋮ Adaptive packet scheduling over a wireless channel under constrained jamming ⋮ Two queues with non-stochastic arrivals ⋮ Adversarial multiple access channels with individual injection rates ⋮ Competitive buffer management with packet dependencies ⋮ Optimal Packet-Oblivious Stable Routing in Multi-hop Wireless Networks ⋮ Stable scheduling in transactional memory ⋮ Stability of adversarial Markov chains, with an application to adaptive MCMC algorithms ⋮ Stability of decentralized queueing networks beyond complete bipartite cases ⋮ Universal stability in multi-hop radio networks ⋮ Packet forwarding with swaps ⋮ The Distributed Wireless Gathering Problem ⋮ Performance of scheduling policies in adversarial networks with non-synchronized clocks ⋮ Online stochastic optimization under time constraints ⋮ The robustness of stability under link and node failures ⋮ Instability behaviour of heterogeneous multimedia networks under dynamic adversarial attacks ⋮ The Effects of Local Randomness in the Adversarial Queueing Model ⋮ On Scheduling Policies for Streams of Structured Jobs ⋮ Coordination Problems in Ad Hoc Radio Networks ⋮ Self-stabilizing repeated balls-into-bins ⋮ Adversarial models for priority‐based networks ⋮ On the power of lookahead in on-line server routing problems ⋮ An excursion-theoretic approach to stability of discrete-time stochastic hybrid systems ⋮ The chilean highway problem ⋮ Stability bounds in networks with dynamic link capacities ⋮ On deciding stability of multiclass queueing networks under buffer priority scheduling policies ⋮ The increase of the instability of networks due to quasi-static link capacities ⋮ An adversarial queueing model for online server routing ⋮ Optimal Algorithms for Detecting Network Stability ⋮ Adversarial queuing theory with setups ⋮ UNIVERSAL ROUTING AND PERFORMANCE ASSURANCE FOR DISTRIBUTED NETWORKS ⋮ Local queuing under contention ⋮ A mathematical model for the TCP tragedy of the commons ⋮ A note on models for non-probabilistic analysis of packet switching networks. ⋮ Broadcasting in ad hoc multiple access channels ⋮ Broadcasting in Ad Hoc Multiple Access Channels

This page was built for publication: Adversarial queuing theory