Technical Report CS-2005-03

TR#:CS-2005-03
Class:CS
Title: On Distributed Smooth Scheduling
Authors: Ami Litman, Shiri Moran-Schein
PDFCS-2005-03.pdf
Abstract: This paper studies evenly distributed sets of natural numbers and their applications to scheduling in a distributed environment. Such sets, called {\em smooth sets}, have the property that their quantity within each interval is proportional to the size of the interval, up to a bounded additive deviation; namely, for $\rho,\Delta\in\reals$ a set $A$ of natural numbers is {\em $(\rho,\Delta)$-smooth} if $\mbox{abs}(\card{I}\cdot \rho-\card{I\cap A})<\Delta$ for any interval $I\subset \naturals$. The current paper studies scheduling {\em persistent clients} on a single slot-oriented {\em resource} in a flexible, predictable and distributed manner. Each client $\gamma$ has a given {\em rate} $\rho_\gamma$ that defines the share of the resource he is entitled to receive and the goal is a {\em smooth schedule} in which, for some predefined $\Delta$, each client $\gamma$ is served in a $(\rho_\gamma,\Delta)$-smooth set of slots (natural numbers). The paper focuses on a {\em distributed environment} where each client by itself (without any inter-client communication) {\em resolves} (computes), slot after slot, whether or not it owns this slot. The paper presents extremely efficient schedules under which a client resolves each slot in a constant time. The paper considers two scheduling frameworks. The first one, the {\em Flat Scheduling Framework}, is the common problem where the rates of the clients are given a priori. In the second and novel framework, the {\em Open-Market Scheduling Framework}, fractions of the resource are bought and sold by {\em dealers}. Each dealer, upon receiving his fraction, may choose either to become a client and use his share, or to remain a dealer and sell fractions of his share to other dealers. In this framework, the allocation process is highly distributed; moreover, fractions of several resources can be combined into a single virtual resource of new capabilities. The paper presents two scheduling techniques. Both techniques, in both frameworks, produce smooth schedules with highly efficient distributed resolutions --- a client resolves each slot in $O(1)$ time on a RAM with a moderate number of memory words, all of a small size. Each technique has its pros and cons. For example, one technique utilizes $100\%$ of the resource but its resolution algorithm requires a number of words which is linear in the number of clients; the other technique utilizes only $99\%$ of the resource but its resolution algorithm requires just $O(1)$ words. One of these techniques yields a solution to Tijdeman's Hierarchial Chairman Assignment Problem which outperforms prior solutions. The other technique naturally extends to the problem of scheduling multiple resources, under the restriction that a client may be served concurrently by at most one resource. The extension yields the first solution to this problem having efficient distributed resolution. Prior solutions produce a special type of smooth scheduling called {\em P-fair scheduling}, are centralized, and are less efficient than ours.
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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2005/CS/CS-2005-03), 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 2005
To the main CS technical reports page

Computer science department, Technion
admin