Non-clairvoyant assignment of bag-of-tasks applications across multiple clouds

Bag-of-Tasks applications are often composed of a large number of independent tasks, hence, they can easily scale out. With public clouds, the (dynamic) expansion of resource capacity in private clouds is much facilitated. Clearly, cost efficiently running BoT applications in a multi-cloud environment is of great practical importance. In this paper, we investigate how efficiently multiple clouds can be exploited for running BoT applications and present a fully polynomial time randomized approximation scheme (FPRAS) as a novel task assignment algorithm for BoT applications. The resulting task assignment can be optimized in terms of cost, make span or the tradeoff between them. The objective function incorporated into our algorithm is devised in the way the optimization objective is tunable based on user preference. Our task assignment decisions are made without any prior knowledge of the processing time of tasks, i.e., non-clairvoyant task assignment. We adopt a Monte Carlo sampling method to estimate unknown task running time. The experimental results shows our algorithm approximates the optimal solution with little overhead.