Li Zhang, Fang Wu and
Bernardo A. Huberman
HP Laboratories
Palo Alto, CA 94304
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 non- cooperative 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 or 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.
Full paper: queues.pdf
|
printable version
