The k-Client Problem |
| |
Authors: | Houman Alborzi Eric Torng Patchrawat Uthaisombut Stephen Wagner |
| |
Affiliation: | a Department of Computer Science, University of Maryland, College Park, Maryland, 20742;b Department of Computer Science and Engineering, Michigan State University, East Lansing, Michigan, 48824 |
| |
Abstract: | 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 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. |
| |
Keywords: | online algorithms multithreaded systems disk scheduling competitive analysis maximum response time average completion time |
本文献已被 ScienceDirect 等数据库收录! |
|