Ph.D Thesis

Ph.D StudentMoran Shiri
SubjectRate Based Sequences and Smooth Scheduling
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Ami Litman
Full Thesis textFull thesis text - English Version


This work studies evenly distributed sets of natural numbers and their applications to scheduling. Such sets, called 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 ρ,Δ‎\inR a set of natural numbers is (ρ,Δ)-smooth if abs(|I|∙ρ-|I∩A|)<Δ for any interval I .  The work studies applications of smooth sets to common and well studied scheduling problems.

The first chapter introduces the concept of smooth sets and studies their mathematical structure. It focuses on tools for constructing smooth sets having certain desirable properties. The rest of the work builds on this mathematical infrastructure and studies scheduling persistent clients on a single slot-oriented resource. Each client γ has a rate ργ  defining the share of the resource he’s entitled to receive; the goal is a smooth schedule in which, for some predefined Δ, each client γ is served in a γ)-smooth set of slots.

The second chapter studies a distributed environment where each client by itself (without any inter-client communication) resolves, slot after slot, whether he owns this slot. This chapter presents schedules under which a client resolves each slot in a constant time. The chapter introduces the novel Open-Market Scheduling Framework in which fractions of the resource are recursively bought and sold by dealers. In this framework fractions of several resources can be combined into a single virtual resource of new capabilities.

The third chapter considers a centralized environment where a single algorithm computes the user of the current slot. The chapter presents a centralized smooth scheduler that computes the user of each slot in, essentially, O(1) time. The scheduling techniques of the second and third chapters are easily extended to the multiple resources framework, and this even in the harder non-concurrent environment: under the restriction that a client can be served concurrently by at most one resource.

The last chapter considers, in the multiple resources framework, the case where the rates of the clients vary in time. In this framework, a schedule is Δ-smooth if for all time intervals I the absolute difference between the service received by each client to his nominal requirement is less than Δ. The work introduces the first online schedulers for the problem that produce Δ-smooth schedules where Δ is a small constant. Furthermore, it extends these results for the non-concurrent environment and provides some insights concerning the similarity and difference between the non-concurrent and concurrent environments.