Towards Elastic Algorithms as a New Model of Computation for the Cloud

Abstract

Cloud computing has emerged as a cost-effiective way for delivering metered computing resources. It supports a Pay-as-you-go model of computation in which users pay only for the resources used, when used. Within this context managing resource elasticity has become an active research topic for the research community. A major focus of such research has been on investigating various approaches to support dynamic scaling of the resources used so as to match the users computational demands while minimising the cost of using such resources. However, little or no work has investigated the concept of supporting algorithm elasticity itself, i.e. organizing the users computation to adapt dynamically to resource availability and cost. In this paper we introduce the concept of an elastic algorithm (EA), and algorithm that structures the computation to make use of the Pay-as-you-go paradigm. In contrast to conventional algorithms, where a computation is typically regarded as a deterministic process that only produces an all-or-nothing result, an EA is organized to generate a sequence of approximate results corresponding to its resource consumption. On a tight resource budget the algorithm guarantees producing an approximate useful result. However, if the user has more budget, and accordingly can use more resources, an EA guarantees producing better results. In this sense, the quality of the algorithm output becomes elastic to its resource consumption. In this paper, we formalize the properties of algorithm elasticity and also formalize the key features of an EA. We illustrate the key concepts by designing an elastic kNN classification algorithm and discussing its key elastic features. We also describe a number of key challenges that need to be addressed when designing EAs in general and set them as a research agenda for the community.