Abstract
Cloud computing often utilizes "Bag of Tasks" (BoT) models for parallel processing. However, when tasks depend on geographically distributed data sources—a model termed "Bag of Distributed Tasks" (BoDT)—traditional centralized execution faces significant latency penalties. This paper explores a heuristic framework designed to optimize BoDT execution by balancing performance gains against monetary costs. Using a tunable preference parameter ($\beta$), the proposed system identifies optimal deployment plans across global cloud regions, demonstrating that decentralized execution can offer superior speed and cost-efficiency compared to traditional centralized models.
Introduction
The "Bag of Tasks" (BoT) model is a cornerstone of parallel computing, consisting of independent, identical jobs that can be executed concurrently. In standard cloud environments, these are typically processed in a single data center. However, the emergence of globally distributed data has led to the "Bag of Distributed Tasks" (BoDT). In BoDT, each task requires input data from a specific geographic location, introducing a critical dependency on network latency and data locality.
The BoDT Challenge
Executing BoDT centrally forces data to travel across long distances, incurring high communication costs and latency. Conversely, deploying virtual machines (VMs) in every region near data sources minimizes latency but can skyrocket costs because cloud providers typically charge for resources in fixed time blocks (e.g., hourly).
As illustrated in Figure 1, the BoDT model adds a significant data retrieval step between the executor and the data source, which is absent in standard BoT. The challenge for cloud users is finding the "Goldilocks" zone: determining the optimal number and location of VMs to satisfy specific budget constraints and performance requirements.
Methodology
The authors propose a multi-stage heuristic framework to navigate this trade-off without the computational overhead of exhaustive constraint programming. Their framework consists of four key algorithms:
- Nearest Plan: Initially assigns every task to the cloud VM geographically closest to its data source to minimize transfer time.
- Reduce Time Block: Iteratively moves tasks between VMs to minimize the total number of charged hours by packing tasks into fewer instances.
- Balancing Algorithm: Shifts tasks from overloaded VMs to underloaded ones to ensure all VMs finish at roughly the same time, reducing the overall makespan.
- Find Plan Algorithm: A master controller that uses a preference factor, $\beta$ (where 0 is "cheapest" and 1 is "fastest"), to score different deployment plans and select the one that best matches user priorities.
Experimental Evaluation
The researchers evaluated their framework using a real-world distributed setup involving 3,290 text files distributed across 47 nodes on PlanetLab, a global research network. Execution was performed on Amazon Web Services (AWS), utilizing 8 different geographic regions. A distributed "word count" program served as the benchmark application.
Key Results and Trade-offs
The study reveals that decentralized execution is often both faster and more cost-effective than centralized approaches. By reducing the time spent waiting for data transfers, tasks finish faster, often fitting into fewer billable hour blocks. For example, a centralized plan took over 11,000 seconds, while a 3-VM decentralized plan took roughly 3,100 seconds—a massive performance gain for a lower or equal cost.
Figure 5 illustrates the non-linear relationship between cost and performance. While increasing the number of VMs generally improves speedup, the cost increase does not scale proportionally. Notably, the centralized plan exhibited significantly lower speedup despite higher relative costs compared to optimized decentralized plans. The heuristic algorithm successfully predicted the optimal plan in 10 out of 11 tested scenarios (91% accuracy).
Conclusion
The proposed heuristic framework effectively manages the complexities of BoDT execution on the cloud. By abstracting the cost-performance trade-off into a single parameter, it allows users to align cloud deployments with specific Service Level Agreements (SLAs) without requiring deep knowledge of network topology. Future directions include investigating heterogeneous VM types and dynamic scheduling to better handle real-world network instability.
Summary updated