M.Sc Thesis

M.Sc StudentYaniv Jonathan
SubjectTruthful Mechanisms for Value-Based Scheduling in Cloud
DepartmentDepartment of Computer Science
Supervisor PROF. Joseph Naor
Full Thesis textFull thesis text - English Version


Cloud computing provides an attractive computation platform, in which computing resources (e.g., virtual machines, storage capacity) are rented to end-users under a utility pricing model. The most common pricing offering is a pay-as-you-go scheme, in which users are charged a fixed price per unit resource per hour. While this scheme is simple to implement, it does not support value-based scheduling, where users assign a value to their job and the cloud's goal is to schedule jobs to maximize aggregate value under job demand and capacity constraints.

In this work, we introduce a novel pricing and allocation approach for batch jobs (e.g., image processing, financial analytics, scientific simulations) on cloud systems. In our economic model, users submit jobs with a value function that specifies willingness to pay as a function of job due dates. The cloud provider in response allocates a subset of these jobs, taking into advantage the flexibility of allocating resources to jobs in the cloud environment. Focusing on social-welfare as the system objective (especially relevant for private or in-house clouds), we construct a resource allocation algorithm which obtains a small approximation factor that approaches 2 as the number of servers increases, assuming that user valuations are known.

An appealing property of our scheme is that jobs are allocated non-preemptively, i.e., jobs run in one shot without interruption. This property has practical significance, as it avoids significant network and storage resources.

Based on this algorithm, we then design an efficient truthful-in-expectation mechanism, which significantly improves the running complexity of black-box reduction mechanisms that can be applied to the problem, thereby facilitating its implementation in real systems.