<figure><img src="image_1.png" /></figure>

HAL
open science

# Boosting Task-Driven Applications from Cloud to Edge: Leveraging Utility for Effective Data Replication

Cherif Si Mohammed, Adrien Lebre, Alexandre van Kempen

► To cite this version:

Cherif Si Mohammed, Adrien Lebre, Alexandre van Kempen. Boosting Task-Driven Applications from Cloud to Edge: Leveraging Utility for Effective Data Replication. IC2E 2025 - 13th IEEE International Conference on Cloud Engineering, Sep 2025, Rennes, France. pp.1-9. hal-05233840

HAL Id: hal-05233840

https://hal.science/hal-05233840v1

Submitted on 1 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Boosting Task-Driven Applications from Cloud to Edge: Leveraging Utility for Effective Data Replication

Cherif SI MOHAMMED

STACK team, ADEME, LS2N,
IMT Atlantique

Nantes, France

cherif.simohammed@ademe.fr

Adrien LEBRE

STACK team, Inria, LS2N,
IMT Atlantique

Nantes, France

adrien.lebre@inria.fr

Alexandre VAN KEMPEN

Qarnot Computing

Montrouge, France

alexandre.vankempen@qarnot-computing.com

**Abstract**—The ongoing shift from Cloud Computing to Edge Computing paradigm brings geo-distributed data management challenges back to the forefront, particularly in the context of large-scale data processing.

This article explores data replication, a key strategy for improving system performance in geo-distributed computing environments. While replication can improve efficiency, naive strategies often result in excessive and unnecessary data transfers, leading to inefficient resource utilization, particularly in infrastructures interconnected via heterogeneous network links. To address these limitations, we propose a replication strategy that estimates the utility of each potential replica before deployment. The approach is first evaluated in homogeneous environments and then extended to heterogeneous settings with varying network characteristics. Simulation results show that our method significantly reduces data transfers while maintaining high execution efficiency, achieving a balanced trade-off between performance and resource consumption.

***Index Terms***—Geo-distributed, replication, scheduling, energy efficiency, Bag of tasks.

## I. INTRODUCTION

Since the emergence of Cloud Computing [1], IT infrastructures have undergone a radical transformation. By providing access to powerful and scalable computing resources, the cloud has enabled organizations to deploy applications and services on a large scale without having to invest heavily in physical infrastructures. Major industry players such as Amazon Web Services, Google Cloud, and Microsoft Azure have been at the forefront of this evolution, providing businesses with the necessary tools to expand their computing operations globally [2].

As demand for high-performance computing and large-scale data storage has increased, along with evolving international regulations on data storage [3], the centralized Cloud model has begun to show its limitations. Modern applications and use cases, which generate massive amounts of data and require significant computational power with near-instant resource availability, have highlighted challenges related to data availability, network latency, and fault tolerance. To address these challenges, centralized Cloud infrastructures have gradually transitioned to geo-distributed ones, where computing power

and storage are distributed across multiple geographical locations [4]. This shift brings computational resources closer to users, enabling faster access and improved fault tolerance [5].

However, as geo-distributed infrastructures expand, the complexity and energy costs associated with resource management continue to grow due to increasing data volumes and higher communications overhead [6]. One of the major challenges in these infrastructures is data management; regardless of the data type, data must be continuously exchanged across geographically dispersed sites to ensure optimal performance, as end-users are distributed. As an example, in distributed computing infrastructures, optimizing data placement can help reduce execution time [7]. In contrast, poor data management can lead to excessive data transfers and inefficient storage usage, which can result in high bandwidth and energy costs, increased latency, and network congestion risks [8]. To overcome these limitations, selecting an effective data management strategy in geo-distributed environments is crucial for ensuring optimal performance while maintaining cost efficiency.

In this work, we present a comprehensive study focused on the design of a replica management policy that seeks to balance system performance with data transfer costs in distributed computing environments. We specifically address infrastructures that execute jobs composed of multiple independent tasks operating over shared datasets, commonly known as bags of tasks. In contrast to conventional approaches that primarily aim to maximize data availability and job performance [9]–[14], our method explicitly integrates the cost of dataset transfers into the decision-making process. The main contributions of this paper are as follows: First, we propose a replication policy based on replica utility to guide decision making in homogeneous network environments for bags-of-tasks. Second, we adapt the proposed approach to operate effectively in more heterogeneous network configurations. Our simulations demonstrate the effectiveness of this utility-based strategy in improving overall performance, more specifically, by reducing the average flow time of executed jobs. Furthermore, the results highlight promising avenues for incorporating fairness criteria into the replication strategy.
The remainder of this paper is structured as follows. Section II presents the motivation for this work and defines the problem statement. Section III describes our proposed approach in detail, addressing both homogeneous and heterogeneous environments. Section IV provides an empirical evaluation of the method. In section V, we present some related works. Finally, Section VI concludes the paper and outlines potential directions for future research.

## II. MOTIVATION AND PROBLEM STATEMENT

### A. Motivation

The rapid evolution of distributed computing infrastructures is accompanied by an exponential growth in the volume of data processed and exchanged. This phenomenon makes data management, particularly replica management, increasingly critical. Whereas the datasets utilized in such environments were initially on the order of megabytes, contemporary data volumes frequently reach several gigabytes or even terabytes. This substantial augmentation in dataset size results in significantly elevated transfer costs, encompassing both bandwidth utilization and energy consumption.

Based on this, we aim to develop a more effective approach for balancing cost and performance in distributed computing systems. Unlike traditional methods, which often prioritize performance at the expense of cost efficiency [9]–[12], our focus is on recognizing and optimizing data transfer costs as a critical factor. We believe these costs are significant enough to warrant direct consideration during scheduling and resource allocation. Therefore, our goal is to design a data management policy that leverages available information on computational jobs, infrastructure, and datasets to achieve a meaningful trade-off between minimizing costs and preserving performance.

<figure><img src="image_3.png" /><figcaption>Fig. 1: Architecture of the targeted infrastructure</figcaption></figure>

### B. Problem Statement

This study investigates a distributed computing environment comprising *M* client nodes, each directly connected to a central master node responsible for coordinating job execution and distributing datasets, as depicted in Figure 1. The infrastructure executes jobs, denoted by $j = (T_j, D_j)$, where $T_j = \{t_1, t_2, \dots, t_{n_j}\}$ is a set of tasks for job *j*, and $D_j$ is a static, immutable dataset of fixed size $d_j$, shared among all tasks in $T_j$. Tasks run sequentially on a node: when one task finishes on a node, another starts.

In large-scale computing environments, a single dataset can be shared across multiple parallel tasks to efficiently

execute complex jobs. This approach is common in fields like climate modeling, computational biology, particle physics, and 3D rendering, where different processing steps—such as simulation, analysis, reconstruction, or rendering—can operate simultaneously on the same data.

The objective is to develop a replica management strategy that determines the number of replicas of a dataset $D_j$ and their allocation across nodes. This strategy, based on job characteristics (e.g., number of tasks $n_j$, dataset size $d_j$) and infrastructure configuration (e.g., available bandwidth, nodes), aims to maximize system performance while maintaining acceptable overhead.

We consider two network configurations:

* **Homogeneous Configuration:** All nodes have identical bandwidth, i.e., $\forall i, j, b_i = b_j$.

* **Heterogeneous Configuration:** Bandwidth varies across nodes, i.e., $\exists i, j$ such that $b_i \neq b_j$.

This dual analysis evaluates the strategy's adaptability under varying network constraints.

### C. Assumptions

In the remainder of this work, we adopt the following assumptions, which hold regardless of the network configuration (homogeneous or heterogeneous):

* **Node Homogeneity:** The computation capability of all client nodes is identical.

* **Unlimited Storage:** Each node has unlimited local storage, satisfying $Z_i \ge d_j$ for all $i \in \{1, \dots, M\}$ and job *j*, ensuring any node can host a replica of $D_j$.

* **Uniform Task Execution Time:** All tasks in $T_j$ of a job *j* have identical execution times, i.e., $\forall t_k, t_l \in T_j, \tau_k = \tau_l$.

* **Known Number of Tasks:** For each job *j*, the number of tasks $|T_j| = n_j$ is known and fixed prior to scheduling.

## III. PROPOSED APPROACH

In this section, we present and detail our replica management approach. We begin by describing the method in the context of a homogeneous network infrastructure and then extend it to the heterogeneous case.

### A. Case 1: homogeneous network

The proposed approach is based on the concept of the *utility* of a replica of the $D_j$ dataset on a node *i*. This utility represents, in other words, the importance of a replica and its impact on performance. It's defined as the ratio between the cost of transferring the replica to the node *i*—estimated as transfer time—and the cumulative execution time of the tasks that use the replica and are assigned to that node.

The algorithm computes this utility *prior to deployment*, in order to decide whether it is beneficial to replicate the dataset on a given node.

The details of the approach are as follows: When a job arrives in the system, a node is randomly selected from the available ones—either currently free or the next to become free, the dataset is transferred to that node, and execution of tasks begins immediately (after each task is finished on a node,
another one is sent); else the job is added to a waiting list until one node is available. This first node becomes the reference node for the job. The reference node is then responsible for monitoring the execution of the tasks associated with the job and notifying the master node based on the evaluation of two predefined conditions.

Let $C_{ij}$ denote the transfer cost (i.e., transfer time) of the dataset of job $j$ to node $i$, and let $S_i$ be the start time of the current task running on node $i$. The two conditions for triggering a replica are:

* **Condition 1:** If the task of the job $j$ on the node $i$ has finished with an execution time $\tau_j$ less than the dataset transfer time.

$$ \tau_j < C_{ij} \qquad (1) $$

* **Condition 2:** If the execution time of the current task on the node $i$ exceeds the transfer time $C_{ij}$.

$$ C_{ij} < (t_{\text{now}} - S_i) \qquad (2) $$

If one of the conditions is met on the reference node, a notification is sent to the master node. The master node then checks whether there are available nodes and, if so, computes the subset $V$ of nodes that satisfy condition in the equation 3. Once this subset is selected, the master initiates the transfer of replicas and starts new tasks of the job $j$ on those nodes.

$$ \forall i \in V, \quad U(d_j, i) \le \theta \qquad (3) $$

where $V$ represents the subset of nodes selected for replicating the dataset $d_j$ and assigned to job $j$, $\theta$ is an arbitrary threshold used to evaluate this utility, and $U(d_j, i)$ represents the utility of placing a new replica of $d_j$ on node $i$, it's calculated using the equation 4 below:

$$ U(d_j, i) = \frac{C_{ij}}{u_{j,i}} \qquad (4) $$

with $u_{j,i}$ representing the duration during which the replica of the dataset $d_j$ will be used.

To estimate the expected usage time of a future replica, we can, in this case, take a clairvoyant approach based on the available information:

* We know the number of replicas that dataset $d_j$ currently has on the infrastructure.

* We also know that the numbers of tasks on a job $j$ denote $n_j$ that all tasks have approximately the same execution time and the infrastructure is homogeneous; the execution time $\tau_j$ will not vary significantly from one node to another. In case of **Condition 2** (2), we consider $\tau_j \ge C_{ij}$ until a task is finished.

Based on this, we can estimate the number of tasks that will be executed on the node hosting the new replica. To do so, we consider the number of tasks from the job $j$ that remain in time $t_{\text{now}} + C_{ij}$, the moment that transfer ends. With this information, we can estimate how many tasks will be assigned to node $i$, and thus estimate the expected usage time of the replica.

We define the estimated number of tasks $P_{j,i}$

$$ P_{j,i} = \frac{|T_j| - N_j(t_{\text{now}} + C_{ij})}{R_j + 1} \qquad (5) $$

where $N_j(t)$ denotes the number of job $j$'s tasks executed up to time $t$, $C_{ij}$ is the cost considered as the transfer time, and $R_j$ is the total number of replicas of dataset $D_j$ already available.

Then, assuming a constant execution time $\tau_j$ per task, the estimated usage time of the replica is:

$$ u_{j,i} = P_{j,i} \cdot \tau_j \qquad (6) $$

Based on this, if we have at least one candidate node, it is sufficient to verify the following condition for one node $i$ in order to proceed with adding a replica of the dataset $d_j$:

$$ U(d_j, i) = \frac{C_{ij}}{\frac{|T_j| - N_j(t_{\text{now}} + C_{ij})}{R_j + 1} \cdot \tau_j} < \theta \qquad (7) $$

This condition is valid for adding a replica of job $j$ on node $i$, ensuring that transfers remain useful and avoiding unnecessary ones. However, in our case, we aim to directly compute the number of replicas that can be added simultaneously. To achieve this, we propose Algorithm 1, which computes the maximum number of replicas that can be added based on the number of available candidate nodes, while ensuring that the utility remains $\le \theta$.

**Algorithm 1 Utility-Based replication algorithm**

1: **Input:** Job $j$, threshold $\theta$

2: **Outputs:** $\text{nodes\_to\_use}$: list of node to use

3: get the list of available candidate nodes $c\_\text{nodes}$

4: $\text{nodes\_to\_use} \leftarrow []$

5: $nb\_r \leftarrow 0$

6: **for** each $\text{node}_i$ in $c\_\text{nodes}$ **do**

7: Estimate the transfer time $C_{ji}$ of the dataset $d_j$ to the node $i$

8: $P_{j,i} = \frac{|T_j| - N_j(t_{\text{now}} + C_{ij})}{R_j + nb\_r + 1}$

9: $u_{j,i} = P_{j,i} \cdot \tau_j$

10: $U(d_j, i) = \frac{C_{ij}}{u_{j,i}}$

11: **if** $U(d_j, i) \le \theta$ **then**

12: add $i$ to $\text{nodes\_to\_use}$

13: $nb\_r \leftarrow nb\_r + 1$

14: **else**

15: **break**

16: **end if**

17: **end for**

In Algorithm 1 at line 3 we mention that we have a list of candidate nodes, where we probably will replicate the dataset $d_j$, this list represents all candidate nodes to which replicas can be sent. It contains two types of nodes:

* **Idle nodes:** which are not assigned to any job and are therefore executing nothing at the current time $t_{\text{now}}$.
* **Active nodes:** which are currently executing jobs, but for which we have been able to estimate the remaining execution time, denoted $l_i$, based on information we have. These nodes are only considered if the dataset transfer time $d_j$ is strictly greater than $l_i$, otherwise using a free node is better.

In this homogeneous replication scenario, preference is given to active nodes. If there are not enough of them available, idle nodes are used to complete the selection.

Every time nodes become available, Algorithm 1 is restarted to see if there are jobs that require new replicas. If so, the nodes are assigned to the job according to a priority of arrival of jobs (FIFO) (i.e., if a node is available, the approach will give priority to the oldest running job).

This strategy has two main benefits: first, it keeps idle nodes available for immediate allocation when new jobs arrive; second, it avoids unnecessarily starting new nodes, thus improving resource efficiency and reducing the infrastructure's energy footprint.

## B. Case 2: Heterogeneous network

In a second phase, we aim to explore a more heterogeneous infrastructure. In this context, we assume that the computing nodes remain homogeneous, but the network links differ. This variability directly affects the dataset transfer time between nodes.

If we apply the previously described algorithm without modification, it becomes difficult to manage transfers efficiently and control the number of replicas in such a heterogeneous environment. Consider, for instance, two nodes:

Node 1 has remaining execution time $l_1 = 10$ units and transfer time $C_{j1} = 5$ units, whereas Node 2 has $l_2 = 20$ units and $C_{j2} = 30$ units.

Following Algorithm 1, Node 1 would be selected because it becomes available sooner. However, if we waited for Node 2, we could benefit from a much faster data transfer due to better network performance. In this scenario, transferring to Node 1 could result in a wasted transfer, where the data arrives too late and the node becomes idle before any task is executed.

Thus, in a heterogeneous context, it is crucial to consider not only the remaining execution time $l_i$ but also the transfer time $C_{ji}$ when choosing replication targets. A more refined strategy is required, the one that balances both computation and communication to improve overall efficiency.

For this case, we modify the way the candidate node vector is selected and sorted, specifically in line 3 of Algorithm 1. This step is now replaced by the function described in Algorithm 2. However, the rest of the approach remains unchanged even for the conditions; we only change the section priority of nodes.

# IV. PERFORMANCE EVALUATION

In order to evaluate performance and identify relevant KPIs, we developed a simulation environment in Python using the SimPy [15] discrete-event simulation library. This environment allows us to simulate the distributed infrastructure under

<caption>**Algorithm 2** Sorting nodes according to Transfer Time and Remaining Execution Time</caption>

1: **Input:** nodes: List of all nodes, j job
2: **Output:** candidate_nodes: List of candidate nodes with estimated start times $W_{ij}$
3: **for** each node i in nodes **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;Compute transfer time $C_{ji}$ for node i
5: &nbsp;&nbsp;&nbsp;&nbsp;Estimate remaining execution time $l_i$ on node i
6: &nbsp;&nbsp;&nbsp;&nbsp;Compute $W_{ij} \leftarrow C_{ji} + \max(0, C_{ji} - l_i)$
7: &nbsp;&nbsp;&nbsp;&nbsp;add $(i, W_{ij})$ to candidate_nodes
8: **end for**
9: **return** candidate_nodes
10: **return** candidate_nodes

study. We also created a bags-of-task framework based on a master/clients design to inject jobs, monitor task execution, and evaluate our proposed approach.

The main advantage of this framework lies in its flexibility: given the lack of publicly available traces to recreate realistic scenarios, it enables us to explore a wide range of possible configurations and simulate diverse cases. It provides a controlled and extensible platform for systematically exploring the design space. It allows fine-grained manipulation of infrastructure-level parameters, such as the number of computing nodes, system load, network latency, and bandwidth, as well as job level characteristics, including the number of submitted jobs, the number of tasks per job, task execution time, and dataset size. This helped us gain a deeper understanding of the behavior and effectiveness of our method under various conditions.

## A. Experimental protocol

Regarding the experimental protocol, the master node creates multiple jobs, with each job consisting of a set of tasks that process a single dataset. These jobs are then injected into the system according to a Poisson distribution [16]. This probabilistic model is used to mimic the realistic arrival patterns of jobs, resulting in a variable load on the infrastructure.

Initially, we compared our utility-based (UB replication) approach with two other strategies: single replica and full replication. The single replica strategy transfers a job's dataset to one node upon arrival, executing all tasks sequentially on that node. The full replication strategy transfers the dataset to all nodes to maximize computing capabilities. However, such a strategy is inefficient for jobs with fewer tasks than available nodes. To address this, we revised the full replication strategy to be more adaptive. In this revised approach, the job's dataset is replicated across available nodes, but the number of replicas does not exceed the number of tasks. Additionally, if the number of available nodes is fewer than the number of tasks when the job arrives, more replicas are created as additional nodes become available during execution. We call this the reactive strategy.

We selected these two approaches because they represent the extremes of the replication strategy spectrum: minimal
replication, which reduces costs but sacrifices performance, and maximal replication, which optimizes performance but incurs high communication overhead.

## B. Metrics

To evaluate the performance of our replica management strategy, we consider a set of temporal metrics at the job level. These metrics provide insights into how data placement and system behavior affect the overall performance of a job from submission to completion. The three main metrics used in this evaluation are described below:

* **Execution Time ($ET_j$):** The time interval between the start of the first data transfer associated with a job $j$ and the completion of the last task in that job. This definition captures both data transfer and computation phases as a single execution window.

* **Waiting Time ($WT_j$):** The time elapsed between the submission of the job $j$ and the beginning of its first data transfer.

* **Flow Time ($FT_j$):** The total time from the submission of job $j$ to the completion of its execution. It can be expressed as:

$$FT_j = WT_j + ET_j$$

This metric reflects the complete turnaround time experienced by the job within the distributed infrastructure.

We simulated two distributed infrastructures. The first demonstrated the relevance of our proposal in a single-site datacenter with homogeneous network constraints between the master node and computing nodes (client nodes). The second simulated a geo-distributed infrastructure with heterogeneous network constraints.

## C. Homogeneous case

We simulated an infrastructure composed of 100 compute nodes and one additional master node. Given the system's homogeneity, the bandwidth is symmetric for all connections between the nodes, and is set to 5 Gbit/s.

Initially, we injected a total of 1,000 jobs. Each job consists of between 1 and 20 tasks, resulting in a total of 10,730 tasks, with an average of 10 tasks per job. The size of the datasets varies between 1 GB and 10 GB, the parameter $\theta$ of our utility algorithm is fixed to 1 for the experiments (a new replica is created only if it will be used for a duration at least equal to its transfer time).

Table I shows the average waiting times, execution times, and the total number of replicas for the three strategies. As expected, the *One Replica* policy minimizes data transfers but results in a significantly higher execution time. At the opposite, the *Reactive* policy, being the most aggressive strategy, represents the other extreme with a high volume of data transfers. In contrast, our strategy strikes a balance between these two extremes, reducing performance by a factor of 1.6 while nearly halving the number of replicas. Although this performance reduction may seem significant, it should be considered in the context of the reactive policy's potential starvation issues,

which result in an average waiting time of nearly 20 seconds. Since a replica is created on each available node, incoming jobs may have to wait before accessing nodes. Therefore, the overall performance loss is not 1.6 but rather 1.4.

<table><caption>TABLE I: Comparison of replication strategies across average waiting times, execution times, and number of replicas.</caption><thead><tr><td>Replication Strategy</td><td>WT (s)</td><td>ET (s)</td><td>#Replicas</td></tr></thead><tbody><tr><td>One Replica</td><td>0</td><td>561.27</td><td>1000</td></tr><tr><td>UB Replication</td><td>0.1</td><td>241.26</td><td>5117</td></tr><tr><td>Reactive Replication</td><td>19.37</td><td>151.52</td><td>9795</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Fig. 2: Amount of Data Transfer per Replication Policy</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 3: Cumulative Distribution Function (CDF) of flow time metric</figcaption></figure>

Figure 2, showing the amount of transferred data, and Figure 3, displaying the cumulative distribution function (CDF) of flow times, confirm the trends discussed earlier. They highlight the benefit of considering transfer costs in the replication decision process, leading to more efficient resource management without significantly degrading job responsiveness.

Figure 4 depicts the utility of replicas metric (the inverse of Equation 4), another important metric to consider. Our strategy achieves utility levels that are significantly more favorable compared to the reactive replication strategy. These values are also much closer to those obtained with the One Replica
approach, which yields the highest utility overall we can obtain. This is expected, as in the One Replica strategy, all tasks of a given job are executed on a single node, allowing for optimal utility accumulation.

<figure><img src="image_6.png" /><figcaption>Fig. 4: Utility Distribution per strategy (higher values correspond to better utility)</figcaption></figure>

To eliminate potential biases and more accurately assess the impact of resource availability, we repeated the experiments under varying system load conditions. To simulate different load levels (30%, 50%, 70%, and 90%), we injected the same set of jobs while varying the lambda parameter of the Poisson probability distribution [16]. Figure 5 shows the CDFs of the flow time under these load scenarios.

Under low to moderate loads (30% and 50%), the reactive method delivers solid performance due to greater resource availability. However, starting at 70% load, our strategy outperforms the naive strategies with lower average flow times, indicating more efficient resource management that reduces waiting times and improves overall execution time while doing less transfers than reactive replication, as presented in Table II.

<table><caption>TABLE II: Table summarizing the number of transfers performed in each experiment with varying load for reactive replication and UB (Homogeneous case)</caption><thead><tr><td>Loads</td><td>Reactive replication</td><td>UB</td></tr></thead><tbody><tr><td>30%</td><td>10694</td><td>8192</td></tr><tr><td>50%</td><td>10668</td><td>8122</td></tr><tr><td>70%</td><td>10499</td><td>7346</td></tr><tr><td>90%</td><td>10480</td><td>7276</td></tr></tbody></table>

The last experiments we performed, aimed to better understand the behavior of our method with a wide diversity of jobs. Specifically, we varied the number of tasks per job while keeping all other parameters constant. In the previous experiment, the number of tasks ranged from 1 to 20, with an average of 10 tasks per job. In this extended analysis, we first

<figure><img src="image_7.png" /><figcaption>Fig. 5: CDF of flow time for different system load levels (30%, 50%, 70%, 90%)</figcaption></figure>

increased the range to 1–50 tasks (with an average of 25), and then to 1–100 tasks (with an average of 50).

Table III and Table IV present the results of the two experiments.

The first point concerns the waiting time, which remains significant across all strategies. As the number of tasks per job increases, individual jobs take longer to complete and must wait for available nodes, exacerbating overall delays (even for the one replica strategy). Regarding the average execution and average flow times, although our strategy consistently outperforms the other two, we were surprised by the relatively high number of total replicas in comparison to the one for the reactive strategy. A closer analysis reveals that the reactive strategy suffers from severe starvation issues, often replicating tasks in a best effort mode only on whatever node is available (in other words, due to the starvation issues, the replicas that could be achieved are strongly limited). At the opposite, our strategy performs selective replication by focusing only on replicas that can significantly reduce overall time. This is illustrated by the average utility of the replicas that is 2.5 higher. This targeted replication leads to improved flow times and a more efficient use of computational resources.

However, these experiments also revealed a limitation of our approach, specifically, the use of a uniform $\theta$ parameter across all jobs. Since $\theta$ determines the perceived utility of replication, jobs involving small datasets but with relatively long durations tend to be prioritized. In contrast, jobs that process larger datasets but consist of shorter tasks may be undervalued, leading to suboptimal replication decisions globally.

This phenomenon is illustrated in Figure 6. The average flow time varies with the system's conditions and does not follow a strictly monotonic trend. Specifically, the blue curve—which represents jobs with an average of 10 tasks—shows a decreasing flow time as $\theta$ increases, indicating that higher utility thresholds can lead to better performance through more effective resource utilization. Conversely, the green curve—corresponding to jobs with an average of 25
<table><caption>TABLE III: Comparison of replication strategies with an average of 25 tasks per job.</caption><thead><tr><th>Replication Strategy</th><th>WT (s)</th><th>ET (s)</th><th>FT (s)</th><th>#Transfers</th><th>Average Utility</th></tr></thead><tbody><tr><td>One Replica</td><td>774.76</td><td>1234.70</td><td>2009.47</td><td>1000</td><td>22.02</td></tr><tr><td>UB Replication</td><td>1351.51</td><td>756.05</td><td>2178.45</td><td>5420</td><td>3.93</td></tr><tr><td>Reactive Replication</td><td>1422.40</td><td>907.73</td><td>2259.29</td><td>5499</td><td>1.61</td></tr></tbody></table>

<table><caption>TABLE IV: Comparison of replication strategies with an average of 50 tasks per job.</caption><thead><tr><th>Replication Strategy</th><th>WT (s)</th><th>ET (s)</th><th>FT (s)</th><th>#Transfers</th><th>Average Utility</th></tr></thead><tbody><tr><td>One Replica</td><td>5601.75</td><td>2401.22</td><td>8002.97</td><td>1000</td><td>43.16</td></tr><tr><td>UB Replication</td><td>7423.27</td><td>1600.31</td><td>9023.59</td><td>5681</td><td>4.97</td></tr><tr><td>Reactive Replication</td><td>7548.85</td><td>1921.36</td><td>9470.21</td><td>6702</td><td>1.86</td></tr></tbody></table>

tasks (rescaled for comparison)—exhibits an increasing trend. In this case, raising $\theta$ results in longer average flow times due to more replicas for some jobs, leading to starvation issues.

This contrast underscores the need for our UB strategy to consider not only the system state and replication utility (i.e., $\theta$), but also the specific characteristics of the workload. While our current work does not explore dynamic tuning of $\theta$, a promising direction for future research would be to adapt this parameter on a per-job basis—taking into account factors such as the number of concurrent jobs, resource availability, and the evolving system load. We propose integrating the notion of acceleration, which can be informed by factors such as job priority, system state (e.g., available resources), or user-defined requirements. This contextual information is leveraged to compute a tailored $\theta$ value for each job. Such an adjustment could improve overall performance or, at the very least, promote a more equitable distribution of resources across jobs.

<figure><img src="image_8.png" /><figcaption>Fig. 6: Impact of Utility Threshold $\theta$ on Flow Time</figcaption></figure>

### D. Heterogeneous case

In the heterogeneous scenario, we retained the same hierarchical architecture and the same number of nodes as in the homogeneous case. The primary difference lies in the network connectivity between the master node and the client nodes. While the homogeneous configuration assumes uniform data transfer costs across all nodes for the same dataset, the heterogeneous configuration introduces variable transfer costs depending on the network constraints of each connection.

Concretely, we assigned different bandwidths to the links connecting the master to each client node. The selected bandwidth values range from 200 Mbit/s to 10 Gbit/s, covering a wide spectrum of real-world Internet access technologies such as 4G, 5G, ADSL, and Fiber-optic networks.

Table V shows the average waiting times, execution times, and the total number of replicas for the three strategies. Our UB strategy achieves the performance among the three methods, outperforming the aggressive approach, which, in this case, resulted in nearly twice as many data transfers with both longer execution and waiting times. This performance gain is due to the fact that replicas are only created when relevant. That is, based on node availability, as well as the time required to transfer a data set and create a new replica.

For instance, consider two nodes, A and B: node A will be free in 5 seconds, but its data transfer time is 30 seconds, while node B will be free in 20 seconds, with a transfer time of 15 seconds. UB Replication chooses to replicate to node B because, although it becomes available later, the data transfer can complete just in time for the node to be ready in 20 seconds. In contrast, reactive replication simply selects the node that is either already free or will become available the soonest, without accounting for transfer time.

Another interesting phenomenon is the case where a naive replication policy can generate useless replicas. Indeed, in a heterogeneous environment where data transfers can be very time-consuming, if a replication policy decides to create a new replica, the transfer cost might be so high that by the time the transfer is completed, all tasks will have already been executed. As a result, the new replica ends up not being used at all. This highlights the importance of assessing the potential utility of a new replica before starting the transfer to avoid wasting network resources and performing unnecessary data transfers.

<table><caption>TABLE V: Comparison of replication strategies in terms of execution time, waiting time, and number of transfers.</caption><thead><tr><th>Replication Strategy</th><th>WT (s)</th><th>ET (s)</th><th>#Transfers</th></tr></thead><tbody><tr><td>One Replica</td><td>0.00</td><td>416.12</td><td>1000</td></tr><tr><td>UB Replication</td><td>0.00</td><td>150.55</td><td>5748</td></tr><tr><td>Reactive Replication</td><td>32.26</td><td>164.48</td><td>10187</td></tr></tbody></table>
<figure><img src="image_9.png" /><figcaption>Fig. 7: Cumulative Distribution Function (CDF) of flow time metric</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 8: Amount of Data Transfer per Replication Policy</figcaption></figure>

Figure 8, showing the amount of data transferred, and Figure 7, displaying the CDF of flow times, confirm our analysis. They highlight the importance of considering the transfer cost of the replica, estimating its utility, and carefully selecting the target node in order to avoid unnecessary overhead. This enables better resource management while ensuring acceptable performance.

The boxplots in Figure 9 illustrate the statistical distribution of the utility metrics (the inverse of Equation 4) of each replication strategy. It is clear that even in a heterogeneous environment, utility is highest in the case of one replica, as all tasks are executed using the same dataset, which represents the highest utility overall we can obtain. We can also observe that our proposal closely matches the performance of the one replica approach, which confirms that, in our case, the replicas are indeed effective with an acceptable utility, and no unnecessary data transfers were performed.

As in the homogeneous simulations, we evaluated the three strategies under load levels of 30%, 50%, 70%, and 90%, using the same load generation method as in the homogeneous case with the same set of jobs. Figure 10 presents four CDF graphs of the flow time metric for each of these load levels. Table VI summarizes the number of transfers performed in each experiment under the different loads for both the UB and reactive replication methods. As illustrated in Figure 10, UB

<figure><img src="image_11.png" /><figcaption>Fig. 9: Utility Distribution per strategy (higher value corresponds to better utility)</figcaption></figure>

has a flow time almost similar to that of the aggressive method (reactive replication) for loads of 30% and 50%, making, in both cases, almost 30% less transfers. This is due, as presented above, to the fact that the same reactive generators transfer that may not be used or their utility is less good with a low impact on performance, while the selection of replicas to be added and destination node allows similar performance in flow time with less data movement.

On the other higher loads (70% and 90%), the UB method performs better. In the case of a 70% load, UB offers a much better flow time with fewer transfers, which indicates better resource management and a better choice of dataset to replicate. At 90% load, the flow time is slightly better for UB with a 30% lower average flow than the reactive method, thanks to better transfer management and more efficient resource management.

<figure><img src="image_12.png" /><figcaption>Fig. 10: CDF of flow time for different system load levels (30%, 50%, 70%, 90%)</figcaption></figure>

To conclude the experiments, and as in the homogeneous scenario, we analyzed the impact of varying the $\theta$ parameter in the UB method based on job size by adjusting the average
<table><caption>TABLE VI: Table summarizing the number of transfers performed in each experiment with varying load for reactive replication and UB (Heterogeneous case)</caption><thead><tr><td>Loads</td><td>Reactive replication</td><td>UB</td></tr></thead><tbody><tr><td>30%</td><td>10685</td><td>7290</td></tr><tr><td>50%</td><td>10599</td><td>7246</td></tr><tr><td>70%</td><td>10023</td><td>6267</td></tr><tr><td>90%</td><td>10103</td><td>6195</td></tr></tbody></table>

number of tasks per job (10, 25, and 50) and exploring $\theta$ values ranging from 0.1 to 1. Figure 11 presents three curves representing these job sizes: red for jobs with an average of 50 tasks, green for 25, and blue for 10. The results confirm the limitations and hypothesis previously established in the homogeneous case and highlight the importance of selecting a $\theta$ value that is well-suited to both the system state and the jobs.

<figure><img src="image_13.png" /><figcaption>Fig. 11: Impact of Utility Threshold $\theta$ on Flow Time</figcaption></figure>

## V. RELATED WORK

Replication strategies are a key mechanism for improving data locality [17], [18], fault tolerance [14], [19], [20], and performance in distributed systems. One of the works closest to ours is that of You et al. [21]. In this study, the authors propose a replication method that estimates the utility of a file before its deployment, based on its popularity. This estimation is made by considering the received requests. From this information, the method makes decisions regarding which data to replicate and where to place it, and by comparing different data items, it also determines which data should be retained on a node.

Other works primarily focus on performance optimization without explicit cost considerations. Tang et al. [22] combine replica management with task scheduling, showing that dynamic replication combined with shortest-turnaround scheduling can significantly improve job execution times.

Bandwidth optimization has also been a major concern [23]–[25]. Chang et al. [23] introduce Latest Access Largest Weight (LALW), selecting files for replication based on recent access patterns to reduce transfer loads. Similarly, Park et al. [24] propose Bandwidth Hierarchy Replication (BHR), exploiting network topology to optimize replica placement

under bandwidth constraints. Further, agent-based approaches like ERDA proposed by Veshisht et al. [12] dynamically adapt replica placement using node bandwidth, load, and computational capacity to reduce task execution times and network congestion.

## VI. CONCLUSION

In the era of large-scale distributed computing, where data frequently crosses national boundaries, minimizing data transfers has become essential to optimize performance and reduce operational costs. Efficient data management strategies can significantly improve system responsiveness and resource utilization in distributed infrastructures.

In this context, we have proposed a replication approach tailored to bags of tasks with data dependencies. By leveraging knowledge about the characteristics of the jobs, our method assigns a utility value to each replica. The experiments conducted on both homogeneous and heterogeneous infrastructures using a simulator demonstrated the method's ability to limit data transfers to cases where they have a significant impact on performance. This enables an effective reduction in the overall volume of transferred data while maintaining good performance.

As a perspective, we plan to further explore the concept of acceleration to address the current limitations of the method. The goal is to personalize the approach for each dataset and make it more adaptive to the system's state. This personalization is expected to improve both the generality and adaptability of the method. In future work, we also aim to extend the applicability of our approach to distributed architectures with diverse topologies, as well as infrastructures composed of nodes with heterogeneous computational and storage capabilities. Another important direction will be to perform comparative evaluations against state-of-the-art approaches in order to assess the robustness, relative performance, and adaptability of our method in real-world scenarios.

## ACKNOWLEDGMENTS

Our work is done in the context of the INRIA-Qarnot-ADEME Pulse project https://www.inria.fr/en/pulse.

## REFERENCES

[1] R. Buyya, J. Broberg, and A. Goscinski, eds., *Cloud Computing: Principles and Paradigms*. Wiley, 1 ed., Feb. 2011.

[2] A. Li, X. Yang, S. Kandula, and M. Zhang, "CloudCmp: comparing public cloud providers," in *Proceedings of the 10th ACM SIGCOMM conference on Internet measurement*, (Melbourne Australia), pp. 1–14, ACM, Nov. 2010.

[3] M. Phillips, "International data-sharing norms: from the OECD to the General Data Protection Regulation (GDPR)," *Human Genetics*, vol. 137, pp. 575–582, Aug. 2018.

[4] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, "Edge computing: Vision and challenges," *IEEE internet of things journal*, vol. 3, no. 5, pp. 637–646, 2016.

[5] P. Kumari and P. Kaur, "A survey of fault tolerance in cloud computing," *Journal of King Saud University-Computer and Information Sciences*, vol. 33, no. 10, pp. 1159–1176, 2021.

[6] A. Beloglazov, R. Buyya, Y. C. Lee, and A. Zomaya, "A Taxonomy and Survey of Energy-Efficient Data Centers and Cloud Computing Systems," in *Advances in Computers*, vol. 82, pp. 47–111, Elsevier, 2011.
[7] M. Wang, J. Zhang, F. Dong, and J. Luo, "Data Placement and Task Scheduling Optimization for Data Intensive Scientific Workflow in Multiple Data Centers Environment," in *2014 Second International Conference on Advanced Cloud and Big Data*, (Huangshan, China), pp. 77-84, IEEE, Nov. 2014.

[8] M. Alizadeh, T. Edsall, S. Dharmapurikar, R. Vaidyanathan, K. Chu, A. Fingerhut, V. T. Lam, F. Matus, R. Pan, N. Yadav, and G. Varghese, "CONGA: distributed congestion-aware load balancing for datacenters," in *Proceedings of the 2014 ACM conference on SIGCOMM*, (Chicago Illinois USA), pp. 503-514, ACM, Aug. 2014.

[9] L. Gao, M. Dahlin, A. Nayate, J. Zheng, et al., "Improving availability and performance with application-specific data replication," *IEEE Transactions on Knowledge and Data Engineering*, vol. 17, no. 1, pp. 106-120, 2005.

[10] T. Amjad, M. Sher, and A. Daud, "A survey of dynamic replication strategies for improving data availability in data grids," *Future Generation Computer Systems*, vol. 28, no. 2, pp. 337-349, 2012.

[11] N. Mansouri, G. H. Dastghaibyfard, and E. Mansouri, "Combination of data replication and scheduling algorithm for improving data availability in data grids," *Journal of Network and Computer Applications*, vol. 36, no. 2, pp. 711-722, 2013.

[12] P. Vashisht, R. Kumar, and A. Sharma, "Efficient Dynamic Replication Algorithm Using Agent for Data Grid," *The Scientific World Journal*, vol. 2014, pp. 1-10, 2014.

[13] H.-I. Hsiao and D. J. DeWitt, "A performance study of three high availability data replication strategies," *Distributed and Parallel Databases*, vol. 1, pp. 53-79, 1993.

[14] C. Amza, A. L. Cox, and W. Zwaenepoel, "Data replication strategies for fault tolerance and availability on commodity clusters," in *Proceeding International Conference on Dependable Systems and Networks. DSN 2000*, pp. 459-467, IEEE, 2000.

[15] N. Matloff, "Introduction to discrete-event simulation and the simpy language," *Davis, CA. Dept of Computer Science*. University of California at Davis. *Retrieved on August*, vol. 2, no. 2009, pp. 1-33, 2008.

[16] P. C. Consul and G. C. Jain, "A Generalization of the Poisson Distribution," *Technometrics*, vol. 15, pp. 791-799, Nov. 1973. Publisher: ASA Website eprint: https://www.tandfonline.com/doi/pdf/10.1080/00401706.1973.10489112.

[17] Z. Guo, G. Fox, and M. Zhou, "Investigation of data locality in mapreduce," in *2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (ccgrid 2012)*, pp. 419-426, IEEE, 2012.

[18] G. Kurian, S. Devadas, and O. Khan, "Locality-aware data replication in the last-level cache," in *2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA)*, pp. 1-12, IEEE, 2014.

[19] R. Guerraoui and A. Schiper, "Fault-tolerance by replication in distributed systems," in *International conference on reliable software technologies*, pp. 38-57, Springer, 1996.

[20] A. El Abbadi, D. Skeen, and F. Cristian, "An efficient, fault-tolerant protocol for replicated data management," in *Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems*, pp. 215-229, 1985.

[21] X. You, G. Chang, X. Chen, C. Tian, and C. Zhu, "Utility-Based Replication Strategies in Data Grids," in *2006 Fifth International Conference on Grid and Cooperative Computing (GCC'06)*, (Hunan, China), pp. 500-507, IEEE, 2006.

[22] M. Tang, B.-S. Lee, X. Tang, and C.-K. Yeo, "The impact of data replication on job scheduling performance in the Data Grid," *Future Generation Computer Systems*, vol. 22, pp. 254-268, Feb. 2006.

[23] R.-S. Chang, J.-S. Chang, and S.-Y. Lin, "Job scheduling and data replication on data grids," *Future Generation Computer Systems*, vol. 23, pp. 846-860, Aug. 2007.

[24] S.-M. Park, J.-H. Kim, Y.-B. Ko, and W.-S. Yoon, "Dynamic Data Grid Replication Strategy Based on Internet Hierarchy," in *Grid and Cooperative Computing* (T. Kanade, J. Kittler, J. M. Kleinberg, F. Mattern, J. C. Mitchell, O. Nierstrasz, C. Pandu Rangan, B. Steffen, M. Sudan, D. Terzopoulos, D. Tygar, M. Y. Vardi, G. Weikum, M. Li, X.-H. Sun, Q. Deng, and J. Ni, eds.), vol. 3033, pp. 838-846, Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. Series Title: Lecture Notes in Computer Science.

[25] J. R. Santos and D. Wetherall, "Increasing effective link bandwidth by suppressing replicated data," in *USENIX Annual Technical Conference*, no. 98, 1998.