## 3 Task Redirection Method
### Task Redirection Algorithm  
To balance the loads among MECSs in a distributed manner, each MECS \(i\) must be able to decide autonomously whether to redirect tasks in \(O_{i}(t)\). If MECS \(i\) decides to redirect tasks, \(i\) must select MECS \(j\) to which it transfers tasks. In addition, MECS \(i\) has to determine the amount of workload to redirect to the selected target MECS \(j\). To make such decisions, each MECS \(i\) exchanges \(\rho_{i}(t)\) with other MECSs at the end of a time slot and calculates the average load.  
\[\bar{\rho}(t)=\frac{1}{|N|}\sum_{j\in N}\rho_{j}(t). \tag{8}\]  
If \(\rho_{i}(t)\leq\bar{\rho}(t)\), \(i\) considers that it is relatively underloaded compared with the other MECSs. Thus, \(i\) does not redirect a task in \(O_{i}(t)\) and moves all the tasks in \(O_{i}(t)\) to \(S_{i}(t)\). By contrast, if \(\rho_{i}(t)>\bar{\rho}(t)\), the load of MECS \(i\) is higher than that of some other MECSs; therefore, \(i\) decides to redirect tasks in \(O_{i}(t)\) to MECS \(j\). We adopt the distributed consensus method in [14] for MECS \(i\) to determine not only a target MECS, but also the amount  
Figure 1: Load balancing problem and task redirection approach.  
of workload that \(i\) redistributes to the selected target MECS. The procedure is shown in Algorithm 1. MECS \(i\) collects a set \(\Delta_{i}(t)\) of MECSs whose loads are lower than \(\rho_{i}(t)\). For each MECS \(j\in\Delta_{i}(t)\), a MECS \(i\) calculates the load difference:  
\[\delta_{i,j}(t)=\frac{\rho_{i}(t)-\rho_{j}(t)}{|N|},j\in\Delta_{i}(t). \tag{9}\]  
Then, MECS \(i\) searches for the MECS \(j^{*}\in\Delta_{i}(t)\) that gives the highest \(\delta_{i,j}(t)\). Since the capacity of MECS \(i\) is \(\mathcal{C}_{i}\), the amount of workload corresponding to \(\delta_{i,j^{*}}(t)\) becomes \(\theta_{i,j^{*}}(t)=\delta_{i,j^{*}}(t)\mathcal{C}_{i}\). Since the total workload imposed by the tasks in \(O_{i}(t)\) is \(o_{i}(t)=\sum_{x\in O_{i}(t)}f_{i,x}\), the amount of workload that \(i\) redirects to \(j^{*}\) is \(a_{i,j^{*}}(t)=\min(o_{i}(t),\theta_{i,j^{*}}(t))\). MECS \(i\) constructs a set \(\Phi_{i,j^{*}}(t)\) of tasks to be transferred to \(j^{*}\) by randomly selecting tasks from \(O_{i}(t)\). Specifically, MECS \(i\) randomly selects tasks from \(O_{i}(t)\) as long as \(\sum_{x\in\Phi_{i,j^{*}}(t)}f_{i,x}<\alpha_{i,j^{*}}(t)\). Then, \(i\) redirects all the tasks in \(\Phi_{i,j^{*}}(t)\) to \(j^{*}\).  
After removing \(j^{*}\) from \(\Delta_{i}(t)\), MECS \(i\) repeats the procedure until \(\Delta_{i}(t)\) is empty or all the tasks in \(O_{i}(t)\) are redirected, whichever comes first. If \(\Delta_{i}(t)\) becomes empty before all the tasks in \(O_{i}(t)\) are redirected, MECS \(i\) moves the remaining tasks to its service queue.  
```
1:\(T_{i}(t)=\Delta_{i}(t)\)
2:if\(T_{i}(t)\
eq\emptyset\)then
3: find \(j^{*}=\arg\max_{j\in T_{i}(t)}\delta_{i,j}(t)\)
4:\(\theta_{i,j^{*}}(t)=\delta_{i,j^{*}}(t)\mathcal{C}_{i}\)
5:\(\alpha_{i,j^{*}}(t)=\min(o_{i}(t),\theta_{i,j^{*}}(k))\)
6: Construct \(\Phi_{i,j^{*}}(t)\)
7: redistribute all the tasks in \(\Phi_{i,j^{*}}(t)\) to \(j^{*}\)
8:\(o_{i}(t)=o_{i}(t)-\sum_{x\in\Phi_{i,j^{*}}(t)}f_{i,x}\)
9:if\(o_{i}(t)\leq 0\)then
10: break
11:else
12:\(T_{i}(t)=T_{i}(t)-\{j^{*}\}\)
13:else
14: move remaining tasks in \(O_{i}(t)\) to its service queue.
```  
**Algorithm 1** Task redirection algorithm.