The k-client problem

Virtually all previous research in online algorithms has focused on single-threaded systems where only a single sequence of requests compete for system resources. To model multithreaded online systems, we define and analyze the k-client problem, a dual of the well-studied k-server problem. In the basic k-client problem, there is a single server and k clients, each of which generates a sequence of requests for service in a metric space. The crux of the problem is deciding which client's request the single server should service rather than which server should be used to service the current request. We also consider variations where requests have nonzero processing times and where there are multiple servers as well as multiple clients. We evaluate the performance of algorithms using several cost functions including maximum completion time and average completion time. Two of the main results we derive are tight bounds on the performance of several commonly studied disk scheduling algorithms and lower bounds of lgk/2 + 1 on the competitive ratio of any online algorithm for the maximum completion time and average completion time cost functions when k is a power of 2. Most of our results are essentially identical for the maximum completion time and average completion time cost functions. (C) 2001 Elsevier Science.