Adversarial queueing theory revisited (Invited talk)

We survey over a decade of work on a classical Queueing, Theory problem; the long-term equilibrium of routing networks. However, we do so from the perspective of Adversarial Queueing Theory where no probabilistic assumptions about traffic patterns are made. Instead, one considers a scenario where an adversary controls service requests and tries to congest the network. Under mild restrictions on the adversary, one can often still guarantee the network's stability. We illustrate other applications of an adversarial perspective to standard algorithmic problems. We conclude with a discussion of new potential domains of applicability of such an adversarial view of common computational tasks.