Ph.D Thesis | |

Ph.D Student | Moran Shiri |
---|---|

Subject | Rate Based Sequences and Smooth Scheduling |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Ami Litman |

Full Thesis text |

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
s

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.