# Technical Report CS-2005-03

 TR#: CS-2005-03 Class: CS Title: On Distributed Smooth Scheduling Authors: Ami Litman, Shiri Moran-Schein PDF CS-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. Copyright The 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.