PhD Oral Exam - Mahtab Masoori, Computer Science

When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.

Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.

Abstract

This thesis explores the Renting Servers in the Cloud problem (\RSiC), which addresses the need for efficient job allocation in cloud computing applications. Jobs arrive in an online manner and need to be assigned to servers. The size of each job is always known at the time of arrival. If the duration of the jobs is also known, the scenario is termed clairvoyant; if the duration is unknown, it is non-clairvoyant. An infinite supply of identical servers is available, each providing one unit of computational capacity per unit of time across all dimensions. A server can be rented at any time and remains rented until all assigned jobs are completed. The cost of an assignment is the sum of the rental periods of all servers. The objective is to allocate jobs to servers in a way that minimizes the overall cost while adhering to server capacity constraints.

We first focus on a scenario where all jobs have equal durations and analyze the performance of two natural algorithms, \NF and \FF. We establish a tight bound of $2$ on the competitive ratio of \NF. For \FF, we consider several restrictions, such as two arrival times, and the dual-core server setting, and prove upper and lower bounds on the competitive ratio of \FF.

Next, we conduct a parameterized analysis of \FF, examining inputs where it utilizes at most $k$ servers simultaneously. We support the theoretical analysis with extensive experimental studies on synthetic data that validate the theoretical insights. Then, through carefully constructed instances, we show that for a large class of well-known algorithms for \RSiC, none of them always outperforms the others.

We then study the multi-dimensional \RSiC setting, where jobs have multi-parameter resource demands (e.g., cores, memory), and servers possess multi-dimensional capacities. We demonstrate a direct sum property of \RSiC, and show how to generalize any algorithm for the 1-dimensional case to the $d$-dimensional case. We also propose a novel clairvoyant algorithm called \Greedy; our experiments demonstrate its superiority over existing algorithms in most scenarios. To evaluate its theoretical performance, a new analytical framework is introduced, generalizing a sub-family of \AF algorithms termed monotone \AF, which includes \Greedy, \FF, \LF, and \MTFtext.

Finally we evaluate both clairvoyant and non-clairvoyant algorithms for \RSiC on real-world data using the the Azure dataset. This establishes a benchmark for future research, and yields results that are sometimes different from those obtained on synthetic data in our work as well as in previous work. We also proposed some new algorithms that are combinations of known algorithms and outperform all existing algorithms in our experiments.