## 4 The PI-Based Task Offloading Algorithm
### General Framework  
In PITO, satellites exchange information with their neighbors via LISLs. Each satellite \(s\in S\) iteratively adds or removes delay-sensitive tasks into or out of its task sequence \(\theta_{s}\), minimizing the global objective \(F(\theta)\). To do this, we first introduce two indicators for each task \(t\in T\), i.e., _removal impact_ and _inclusion impact_. 1. Removal impact: for task \(t\in\theta_{s}\), the removal impact \(\mathcal{R}(\theta_{s}\ominus t)\) indicates the variation of \(F(\theta_{s})\) after removing \(t\) from \(\theta_{s}\); then, we have\[\mathcal{R}(\theta_{s}\odot t)=F(\theta_{s})-F(\theta_{s}\odot t) \tag{19}\]  
where \(F(\theta_{s})\) is the objective value of \(\theta_{s}\), we have \(F(\Theta)=\sum_{s\in S}F(\theta_{s})\). \(\theta_{s}\ominus t\) represents the removal of task \(t\) from \(\theta_{s}\). For completeness, we set \(\mathcal{R}(\theta_{s}\ominus t)=\infty\) for any \(t\
otin\theta_{s}\). 1. Inclusion impact: for task \(t\
otin\theta_{s}\), the inclusion impact \(\mathcal{I}(\theta_{s}\oplus t)\) represents the minimum variation of \(F(\theta_{s})\) after inserting \(t\) into \(\theta_{s}\); then, we have \[\mathcal{I}(\theta_{s}\oplus t)=\min_{p\in\{1,2,\ldots,|\theta_{s}|+1\}}\left\{ F(\theta_{s}\oplus_{p}t)-F(\theta_{s})\right\}\] (20) where \(\theta_{s}\oplus_{p}t\) indicates the inclusion of task \(t\) into the \(p\)-th position of \(\theta_{s}\). Similarly, we set \(\mathcal{I}(\theta_{s}\oplus t)=\infty\) under two states: when \(t\in\theta_{s}\), or when constraints (12) and (13) cannot be satisfied after incorporating task \(t\). To introduce the general framework in Figure 3, let us begin with a straightforward example. Initially, satellite \(s\in S\) adds tasks into its sequence \(\theta_{s}\), following the inclusion rules in Section 4.2. Then, satellite \(s\) sends the removal impact \(\mathcal{R}(\theta_{s}\odot t)\) of all tasks \(t\in\theta_{s}\) to neighboring satellite \(k\) (i.e., \(G[s,k]=1\)) via LISLs. After that, satellite \(k\) evaluates the received \(\mathcal{R}(\theta_{s}\ominus t)\) against the inclusion impact \(\mathcal{I}(\theta_{k}\oplus t)\) derived from its sequence \(\theta_{k}\). If criterion (21) is met, task \(t\) will be reassigned from \(\theta_{s}\) to the appropriate position within \(\theta_{k}\), and then \(F(\Theta)\) decreases. Simultaneously, satellite \(k\) updates the removal impact of \(t\) and relays it to neighboring satellites via LISLs. This process is continued until (21) is no longer met. Then, we introduce Lemma 1 to the detail criterion (21). Lemma 1: _For offloading assignment \(\boldsymbol{\theta}=\{\theta_{1}\), \(\theta_{2}\), \(\ldots\), \(\theta_{m}\)], two satellites \(s\) and \(k\) connect by LISL (i.e., \(G[s,k]=1\)) and a task \(t\in\theta_{s}\backslash\theta_{k}\). The \(F(\boldsymbol{\theta})\) will be decreased by removing \(t\) from \(\theta_{s}\) to an appropriate position within \(\theta_{k}\), as long as (21) is met._  
\[\mathcal{R}(\theta_{s}\ominus t)>\mathcal{I}(\theta_{k}\oplus t) \tag{21}\]  
Proof: Let \(p^{\prime}\) be the optimal position in \(\theta_{k}\), i.e., \(p^{\prime}=\operatorname*{argmin}_{p\in\{1,2,\ldots,|\theta_{k}|+1\}}[F( \theta_{k}\oplus_{p}t)-F(\theta_{k})]\), so we have \(\mathcal{I}(\theta_{k}\oplus t)=F(\theta_{k}\oplus_{p^{\prime}}t)-F(\theta_{ k})\). After removing task \(t\) from \(\theta_{s}\) to the \(p^{\prime}\)-th position of \(\theta_{k}\), a new assignment \(\theta^{\prime}\) is obtained, where \(\theta_{s}^{\prime}=\theta_{s}\ominus t\), \(\theta_{k}^{\prime}=\theta_{k}\oplus_{p^{\prime}}t\), and \(\theta_{l}^{\prime}=\theta_{l}\), \(\forall l\in S/\{s,k\}\). According to (19) and (20), we have \(F(\theta^{\prime})=\sum_{l\in S}F(\theta_{l}^{\prime})=F(\Theta)-\mathcal{R}( \theta_{s}\ominus t)+\mathcal{I}(\theta_{k}\oplus t)\). Thus, \(F(\Theta^{\prime})<F(\Theta)\) holds (i.e., \(F(\Theta)\) decreases) only when \(\mathcal{R}(\theta_{k}\ominus t)>\mathcal{I}(\Theta_{l}\oplus t)\) is met. \(\square\)  
Figure 3: Framework of PITO.