CATS-Dec-4-2015
Title[edit]
Pricing the Cloud
Speaker[edit]
Sina Dehghani
Abstract[edit]
Recently there is an increasing tendency towards using cloud for computation among big businesses. To deal with this we need efficient and simple mechanisms for providing cloud services. In this project, we study online mechanisms for deadline-sensitive non-preemptive cloud scheduling. In particular, we model the problem as an online non-preemptive scheduling problem. Each online demand is a job with an arrival time, a deadline, a length, and a value. We can either accept the job at its arrival and schedule it, or reject the job. The goal is to maximize the total value of the completed jobs.
We consider both adversarial and stochastic variants of the problem. For the adversarial model we provide a truthful mechanism with competitive ratio O(log(V_max/V_min) log(L_max/L_min)), where V_max/V_min and L_max/L_min denote the ratio of the maximum value of the jobs to the minimum value of the jobs, and the ratio of the maximum length of the jobs to the minimum length of the jobs, respectively. For the stochastic variant of the problem we provide a truthful O(log L_max/L_min)-competitive mechanism.
