Offloading of tasks to the cloud is one of the approaches to improve the performance of distributed applications. When monetary constraints are present, selection of the tasks to be offloaded becomes important in order to ensure efficient use of the available cloud resources. This becomes a challenge for large scale distributed applications as the decisions on offloading have to be made locally at the nodes without an exact global view of the system. In our earlier work, we modeled this challenge as a new class of formal problems termed cloudy knapsack problem and derived some theoretical bounds on the solution space for worst case task sequences. In many real world applications, the task sequences have inherent patterns which can be exploited to improve offloading. In this work, we propose a cloud offloading algorithm that exploits these patterns through offline and online learning. Experimental evaluation using realistic datasets for a cloud-assisted peer-to-peer search case study reveals that the proposed solution performs close to a hypothetical omniscient offloading algorithm having a complete view of the system. The proposed cloud-assisted peer-to-peer search engine provides a cost-effective approach to address scalability bottleneck in peer-to-peer search engines.

Formal Concept Analysis (FCA) finds applications in several areas including data mining, artificial intelligence, and software engineering. FCA algorithms are computationally expensive and their recursion tree has an irregular structure. Several parallel algorithms have been implemented to manage the computational complexity of FCA. Most of them assume a shared memory environment where they maintain a shared queue of computational tasks and the workers store and retrieve tasks from that queue. Although the shared queue approach addresses the computation skew by fine grained sharing, it causes communication bottlenecks in a distributed memory environment. In this work, we propose static and dynamic load balancing strategies that are applicable in distributed memory environment. We parallelize the FCA algorithm called Linear time Closed itemset Miner and show that the proposed load balancing strategies effectively deal with the computation skew. They not only distribute the load evenly among the workers but also minimize the communication overhead.

Cloud-assisted approaches for both peer-to-peer systems and mobile apps require optimized use of elastic cloud resources. Due to budget constraints, a subset of the tasks has to be selected for offloading considering context parameters like device battery level and task variability. This leads to the challenging problem of context-sensitive task scheduling on elastic resources with a limited global view, which is not addressed by existing works. We identify a new class of formal problems called cloudy knapsack problems to effectively model the same. Abstracting out the problem formally can spur future independent works related to different variants of the problem and corresponding bounds and optimal algorithms. We illustrate the global view related issues through simulations, identify some theoretical bounds for a variant of cloudy knapsack problems and discuss several open problems.

SUMMARY It is difficult to express the parallelism present in complex computations by using existing higher level abstractions such as MapReduce and Dryad. These computations include applications from wide variety of domains, like Artificial Intelligence, Decision Tree Algorithms, Association Rule Mining, Recommender Systems, Graph Algorithms, Clustering Algorithms, Compute Intensive Scientific Workflows, Optimization Algorithms, and so forth. Their execution graphs introduce new challenges in terms of programmer expressibility and runtime performance such as iterative and recursive computations, shared communication model, and so forth. We propose an extension to MapReduce, called Generate‐Map‐Reduce (GMR), targeted towards modeling these applications. GMR introduces a new Generate abstraction into the MapReduce framework that captures recursive computations. The runtime also supports iterative jobs and a distributed communication model by using shared data structures. We illustrate recursive computations with GMR by modeling complex applications such as simulated annealing, A* search, and adaptive quadrature computation that require recursive spawning of new tasks to handle variable degree of parallelism. GMR runtime supports caching of common data across iterations in memory and local disks. We illustrate how this caching helps in achieving significant speedup for iterative computations by modeling k‐means clustering. Copyright © 2013 John Wiley & Sons, Ltd.

Today, batch processing frameworks like Hadoop MapReduce are difficult to scale to multiple clouds due to latencies involved in inter-cloud data transfer and synchronization overheads during shuffle-phase. This inhibits the MapReduce framework from guaranteeing performance at variable load surges without over-provisioning in the internal cloud (IC). We propose BStream, a cloud bursting framework for MapReduce that couples stream-processing in the external cloud (EC) with Hadoop in the internal cloud (IC). Stream processing in EC enables pipelined uploading, processing and downloading of data to minimize network latencies. We use this framework to meet job deadlines. BStream uses an analytical model to minimize the usage of EC. We propose different checkpointing strategies that overlap output transfer with input transfer/processing and simultaneously reduce the computation involved in merging the results from EC and IC. Checkpointing further reduces job completion time. We experimentally compare BStream with other related works and illustrate performance benefits due to stream processing and checkpointing strategies in EC. Lastly, we characterize the operational regime of BStream.

Skew mitigation has been a major concern in distributed programming frameworks like MapReduce. It is becoming more prominent with the increasing complexity in user requirements and computation involved. We present Chisel, a self-regulating skew detection and mitigation policy for MapReduce applications. The novelty of the approach is that it involves no scanning or sampling of input data to detect skew and hence incurs low overhead, provides better resource utilization and maintains output order and file structure. It is also transparent to the users and can be used as a plugin whenever required. We use Hadoop to implement our skew handling policies. Chisel implements two skew handling policies for mitigating skew. It does late skew detection for map operators i.e at the last wave of map execution, where skewed maps are selected on the basis of remaining time to complete. More maps are created dynamically over remaining data per block. An early skew detection i.e before starting shuffle phase, is done for reduce operator. This prevents the expensive shuffle and sort phases from delaying skew detection and job completion time. Multiple reducers are created per skewed partition, each shuffling data from a subset of total maps and starts processing it when their portion of maps are over. They need not wait for the completion of all the maps. Therefore, the barrier between map and reduce phase no longer remains a constraint for effective resource utilization. Chisel additionally implements an online job profiler to determine the start point of reduce tasks and also modifies the capacity scheduler to distribute reduce tasks evenly in the cluster. Chisel significantly decreases the overall execution time of jobs and increases resource utilization. Improvement depends directly upon the availability of resources in the cluster and skewness in the job.

Optimizing ordered throughput not only improves the system efficiency but also makes cloud bursting transparent to the user. This is critical from the perspective of user fairness in customer-facing systems, correctness in stream processing systems, and so on. In this paper, we consider optimizing ordered throughput for near real-time, data-intensive, independent computations using cloud bursting. Intercloud computation of data-intensive applications is a challenge due to large data transfer requirements, low intercloud bandwidth, and best-effort traffic on the Internet. The system model we consider is comprised of two processing stages. The first stage uses cloud bursting opportunistically for parallel processing, while the second stage (sequential) expects the output of the first stage to be in the same order as the arrival sequence. We propose three scheduling heuristics as part of an autonomic cloud bursting approach that adapt to changing workload characteristics, variation in bandwidth, and available resources to optimize ordered throughput. We also characterize the operational regimes for cloud bursting as stabilization mode versus acceleration mode, depending on the workload characteristics like the size of data to be transferred for a given compute load. The operational regime characterization helps in deciding how many instances can be optimally utilized in the external cloud.