Nimble Algorithms for Cloud Computing

Date Added: Apr 2013
Format: PDF

Cloud computing is a new paradigm where data is stored across multiple servers and the goal is to compute a function of all the data. The authors consider a simple model where each server uses polynomial time and space, but communication among servers being more expensive is ideally bounded by a poly-logarithmic function of the input size. They will dub algorithms that satisfy these types of resource bounds as nimble. The main contribution of the paper is to develop nimble algorithms for several areas which involve massive data and for that reason have been extensively studied in the context of Streaming Algorithms.