The nearly simultaneous emergence of cloud computing and big data analytics has brought on new sets of challenges. Organizations have started to replace their own infrastructure with large computing clusters hosted by cloud providers, such as Amazon and Google, and they buy these services using complex pricing mechanisms. The cloud providers currently provide computing power, while the application hosts are interested in completion of their jobs, irrespective of the computing power needed to complete those jobs. The missing link between the demand (job completion) and the supply (computing power) is a key challenge in the new model.

This paper tries to address exactly this kind of challenge. The authors assume that the jobs are provided along with their completion values and resource requirements, and that the cloud providers can choose the sequence and resources with which to schedule the jobs. They propose an algorithm called GreedyRTL, which sorts the jobs in the order of their marginal values (value to resource ratio) similar to the greedy knapsack algorithm, and then schedules a job if it can be completed within its deadline. It can also reallocate previous resources within some constraints. The authors prove that GreedyRTL is a (C/C-k). (s/s-1) approximation algorithm, where C is the capacity of the cloud, k is the bound on parallelization, and s is the slackness guarantee on the job completion time. “The objective of [... this] algorithm is to maximize the social welfare, which is the sum of [the] values of jobs that are completed before their deadline.”

Like many other interesting algorithms, GreedyRTL itself is easy to describe. The analysis is significantly more involved: it uses the formulation of the problem as a linear program and applies the technique of dual fitting to prove the approximation factor.

In coming years, it is quite conceivable that the model discussed in this work may evolve and prove to be a key contribution of this paper, even more so than the algorithm and the analysis. That is understandable for works in new and rapidly evolving fields, especially considering that our understanding of what exactly should be measured is likely to evolve as well.