| Games and Queues (2008) | |||||||||||||||||
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 own utility. Since the performance of such a blind scheduler is worse than optimal, it induces users to employ strategies that 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 noncooperative and selfish, the problem is that of studying the characteristics of the Nash equilibrium in a large distributed system with no omniscient controls. We study this 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 a certain threshold, it is always better off to be impatient, and when the system load is higher than some other threshold, it is always better to be patient. Between these two thresholds there exists a homogeneous Nash equilibrium with non-trivial properties. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||