Games and Queues

Li Zhang, Fang Wu and Bernardo A. Huberman

Abstract

We consider scheduling in distributed systems from a game
theoretic point view while taking into account queuing theory
methodologies. In this approach no one knows the global state of the system while users try to maximize their utility. Since the performance of such a blind scheduler is worse than the optimal, it induces users to employ strategies to improve their own utilization of the system. One such strategy is that of restarting a request if it is not satisfied in a given time. Since we assume users as non-cooperative and selfish, the problem is that of studying the characteristic of the Nash equilibrium in a large distributed system with no omniscient controls. We study the problem through computer experiments and analytical approaches. 

We obtain exact solutions in situations delimited by two extremes: one in which users never restart an initial request, and another one in which the user's requests are restarted infinitely often. Users can switch between these two behaviors. When the system load is below certain threshold, it is always better off to be impatient, and when the system load is higher than some threshold, it is always better to be patient. Between them there exists a homogeneous Nash equilibrium with non-trivial properties.

PDF