Does the Cloud need new algorithms? An introduction to elastic algorithms

Cloud computing has emerged as a cost-effective way to deliver metered computing resources. Within a Cloud, elasticity of resource usage is typically realized through the 'on-demand' provision principle supported by the 'Pay-as-You-Go' business model. However, little, or no work, has investigated elasticity of algorithms for Cloud computing. In this paper, we introduce novel research on elastic algorithms (EA) where the computation itself is organized in a 'Pay-as-You-Go' fashion. In contrast to conventional algorithms, where computation is a deterministic process that only produces an 'ali-or-nothing' result, an EA generates a sequence of approximate results corresponding to its resource consumption. As more resources are consumed, better results will be derived. In this sense, the quality of the algorithm is elastic to its resource consumption. In the paper, we formalize the proeprties of elasticity and also formalize desirable properties for elastic algorithms themselves. We illustrate the design of an EA for kNN classification in the context of machine learning and discuss its properties. Finally we provide an ambitious agenda for future research in this area.