Technical Report CS-2006-13

Title: Smooth Scheduling Under Variable Rates or The Analog-Digital Confinement Game
Authors: Ami Litman and Shiri Moran-Schein
Abstract: This work considers non-terminating scheduling problems in which a system of multiple resources serves clients having variable needs. The system has $m$ identical resources and $n$ clients; in each {\em time slot} each resource may serve at most one client; in each such slot $t$ each client $\gamma$ has a {\em rate}, a real number $\rho_\gamma(t)$, that specifies his needs in this slot. The rates satisfy the restriction $\sum_\gamma \rho_\gamma(t)\leq m$ for any slot $t$. Except of this restriction, the rates can vary in arbitrary fashion. (This contrasts most prior works in this area in which the rates of the clients are constant.) The schedule is required to be {\em smooth} as follows: a schedule is {\em $\Delta$-smooth} if for all time intervals $I$ the absolute difference between the amount of service received by each client $\gamma$ to his nominal needs of $\sum_{t\in I}\rho_\gamma(t)$ is less than $\Delta$. Our objective are online schedulers that produce $\Delta$-smooth schedules where $\Delta$ is a small constant which is independent of $m$ and $n$. Our paper constructs such schedulers; these are the first online $\Delta$-smooth schedulers, with a constant $\Delta$, for clients with arbitrarily variable rates in a single or multiple resource system. Furthermore, the paper also considers a {\em non-concurrent} environment in which there is an additional restriction that each client is served at most once in each time slot; it presents the first online smooth schedulers for variable rates under this restriction. The above non-concurrent restriction is crucial in some applications (e.g., CPU scheduling). It has been pointed out that this restriction ``adds a surprising amount of difficulty'' to the scheduling problem. However, this observation was never formalized and, of course, was never proved. This paper formalizes and proves some aspects of this observation.

Another contribution of this paper is the introduction of a complete information, two player game called {\em the analog-digital confinement game}. In such a game {\em pebbles} are located on the real line; the two players, the {\em analog player} and the {\em digital player}, take alternating turns and each one, in his turn, moves some of the pebbles; the digital player moves the pebbles backwards by discrete distances while the analog player moves the pebbles forward by analog distances; the aim of the {\em analog player} is to cause one pebble (or more) to escape a pre-defined real interval while the aim of the {\em digital player} is to confine the pebbles into the interval. This game is a convenient framework to study the general question of how to approximate an analog process by a digital one. All the above scheduling results are established via this game. In this derivation, the pebbles represent the clients, the analog player represents the needs of the clients and the digital player represents the scheduler.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2006
To the main CS technical reports page

Computer science department, Technion