Delay-Optimal Distributed Edge Computing in Wireless Edge Networks

In general, a communication scheduling policy can be preemptive such that the network can interrupt the execution of a communication at any time and start to execute another communication [46]. However, we can show that it suffices to focus on non-preemptive policies.

Due to space limitation, only the proofs of some results in this paper are provided (in the appendix). Lemma 1 shows that it is not beneficial to preempt an ongoing communication to execute another communication. Intuitively, this is because preemptive scheduling is typically better than non-preemptive scheduling when tasks become available at different times and the objective is to minimize the total delay of tasks [46]. In contrast, for the problem here, the communications are always available (subject to that a backward communication is after the corresponding forward communication), and the objective is to minimize the algorithm delay which is equal to the maximum delay of communication.

Then we show that it is optimal to schedule all the forward communications before all the backward communications.

Lemma 2 provides the insight that it is always beneficial to schedule any forward communication before any backward communication compared to the other way, as it allows for more time to execute the computations associated with these communications.

Next we show that it is optimal for the wireless network to keep busy between forward communications and between backward communications.

The non-idle optimal policy in Lemma 3 means that the wireless network has no idle period between any two forward communications and between any two backward communications. However, there can be some idle period between the last forward communication and the first backward communication (i.e., between time $t_{1}$ and time $t_{2}$ in Fig. 2). Lemma 3 provides the insight that the wireless network should keep performing communications without any idle period, so as to complete communications as soon as possible, unless it is necessary to wait for some period during which the nodes can perform computations.

In this subsection, we study the optimal allocation of computation workloads to nodes given any communication scheduling policy that satisfies the structural properties discussed in Section IV-A.

The optimal computation allocation can be found by an efficient algorithm that consists of up to three phases as described in Algorithm 1. In particular, in Phase 1, we first allocate computation workloads as much as possible to nodes such that all these workloads can be completed before the last forward communication ends (i.e., before time $t_{1}$ in Fig. 2). If the total workload of the algorithm can be fully allocated in this way, we have found the optimal computation allocation. Otherwise, in Phase 2, we allocate computation workloads as much as possible to nodes such that all these workloads can be completed after the first backward communication starts (i.e., after time $t_{2}$ in Fig. 2). If the remaining workload of the algorithm can be fully allocated in this way, we have found the optimal computation allocation. Otherwise, in Phase 3, we allocate the further remaining workload of the algorithm to nodes such that it can be completed after the last forward communication ends and before the first backward communication starts (i.e., between time $t_{1}$ and time $t_{2}$ in Fig. 2). It can be seen that the computational complexity of Algorithm 1 is $O(N)$, as each phase of the algorithm involves at most $N$ iterations. We establish the optimality of Algorithm 1 as follows.

Proposition 1 provides some interesting insights regarding the optimal computation allocation characterized by Algorithm 1. Intuitively, the optimal policy should reduce the idle computing periods of nodes as much as possible, so as to minimize the algorithm delay. To this end, it allocates workloads to the idle period of each node after its forward communication ends and before the last forward communication (among all nodes) ends, and to the idle period after the first backward communication (among all nodes) starts and before its backward communication starts, until there is no such idle period. The workloads allocated to these idle periods do not increase the algorithm delay, as it remains equal to the total delay of all forward and backward communications. If there is some workload of the algorithm that remains unallocated after the above allocation, it is allocated to all nodes in proportional to their computation rates, such that it incurs an equal computation delay to all the nodes. This delay increases the algorithm delay beyond the delay incurred by communications. As a result of Proposition 1 and Algorithm 1, we can see that when the total workload of the algorithm is sufficient (above some threshold), each node keeps performing its computation between its forward and backward communications. Otherwise, some node is forced to be idle between its forward and backward communications.

In this subsection, based on the structural properties of the optimal communication scheduling in Section IV-A and the optimal computation allocation in  IV-B, we study the optimal scheduling order of communication. Due to the symmetry between forward communications and backward communications, we focus on the scheduling order of backward communications, as the results for forward communications follow similarly. In particular, we consider the optimal scheduling order that minimizes the algorithm delay, given the total computation workload $w$ of the algorithm. Based on the optimal computation allocation found by Algorithm 1, we can transform this problem to an equivalent “dual” form: how to schedule the backward communications, such that the total computation workload $v$ that can be completed after the first backward communication starts (i.e., after time $t_{2}$ in Fig. 2) is maximized?

We first consider the case where nodes have uniform computation rates but can have diverse communication delays. The optimal scheduling order is given as follows.

Proposition 2 means that the optimal policy schedules the longest communication (i.e., with the largest delay) first, and the second longest next, etc, as illustrated in Fig. 3(a). This result provides the following insight: it is better to schedule a longer communication earlier than a shorter one, since it allows for more time for other node(s) to perform computing. As a result, the computing capacities of nodes are most efficiently utilized and thus the algorithm delay is minimized.

Then we consider the case where nodes have uniform communication delays but can have diverse computation rates. The optimal scheduling order is given below.

Proposition 3 means that the optimal policy schedules the communication of the slowest node first, and that of the second slowest node next, etc, as illustrated in Fig. 3(b). The insight from this result is as follows: it is better to utilize a faster node for a longer period than a slower node, so that the computing capacities of nodes are most efficiently utilized and thus the algorithm delay is minimized.

Next we consider the general case where nodes can have diverse computation rates and also diverse communication delays. It is plausible that the optimal policies in the previous two cases can perform well for the case here. However, we can find some counterexamples which show that those policies can result in a solution that is arbitrarily worse than the optimal solution (given in the appendix).

To determine the optimal scheduling order, we can use an exhaustive search by calculating the total computation workload $v$ (that can be completed after the first backward communication starts) for all possible scheduling orders and then finding the optimal one. However, the computational complexity of the exhaustive search is $O(N!)$ which is too high. Therefore, we aim to find a computationally efficient approximation algorithm that can provide performance guarantee in terms of the approximation ratio $v/v^{*}$, where $v^{*}$ is the total computation workload for the optimal scheduling order. It can be shown that the largest delay first and fastest node last policies (which are the optimal policies for the previous two cases, respectively) cannot provide a finite approximation ratio due to ignoring computation rates or communication delays, respectively. Thus motivated, the design of the approximation algorithm here should take into account both factors. In particular, we design a greedy algorithm that calculates the total computation workload $v$ for all possible scheduling orders of the first $k$ communications among all the $N$ communications, where $1\leq k\leq N$, and then finds the optimal order of the first $k$ communications. The scheduling order of the remaining $N-k$ communications can be set arbitrarily. The algorithm is described in detail in Algorithm 2. We can show that this algorithm has a finite approximation ratio as follows.

Proposition 4 shows that there exists a tradeoff between the computational complexity of Algorithm 2 and its approximation ratio, which can be controlled by the parameter $k$. The complexity of the algorithm is $O({N\choose k})$ which is in the order of $O(N^{k})$. Therefore, a larger $k$ means higher complexity which is worse, but also a higher approximation ratio which is better.

In the previous subsections, it is assumed that each node is used to execute the distributed algorithm, such that the forward and backward communications of that node is scheduled regardless of the computation workload allocated to it (even when no workload is allocated). However, it is important and interesting to note that it may not be optimal to use as many nodes as possible to execute the algorithm. This is because using an additional node incurs communication delays which can increase the algorithm delay. This increase can outweigh the decrease of the computation delay due to utilizing the additional node for computing, as illustrated in Fig. 4. Thus motivated, in the following we investigate how to select nodes for executing the algorithm to minimize the algorithm delay.

We first consider the cases where nodes have uniform computation rates or uniform communications delays. For these two cases, we can show that the optimal set of nodes to select is those with the smallest communication delays or the highest computation rates.

Lemma 4 is intuitive as a node with a smaller communication delay or higher computation rate should be preferred over one with a larger communication delay or lower computation rate, respectively. Based on this result, we can use an efficient linear exhaustive search to find the optimal set of nodes. In particular, it calculates the minimum delay for all possible numbers of the “best” nodes (i.e., the $k$ nodes with the smallest communication delays or highest computation rates where $k\in\{1,2,\cdots,N\}$), and then finds the optimal number of the “best” nodes. The computational complexity of the linear exhaustive search is $O(N)$.

Then we consider the general case where nodes can have diverse computation rates and also diverse communication delays. To determine the optimal set of nodes, we may use an exhaustive search that calculates the (approximate) minimum delay for all possible sets of nodes (as the optimal scheduling order of communications is difficult to find), and then finds the optimal set among them. However, the computational complexity of the exhaustive search is $O(2^{N})$ which is too high. Therefore, we can use a greedy algorithm instead as follows: we start with the empty set, and in each iteration we add to this set the node not selected that can reduce the algorithm delay the most, until no such node exists. The computational complexity of this greedy algorithm is $O(N)$. We will analyze the performance of this algorithm in terms of its approximation ratio in our future work.

To illustrate the efficiency of the optimal computation allocation, we compare the algorithm delay under the optimal computation allocation (OCA) found by Algorithm 1, and under equal computation allocation (ECA) that allocates an equal computation workload $w/N$ to each node. We set the default parameters as follows: $N=3$, $w=10$, $s_{i}=1$, $d_{i}=1$, $r_{i}=1$, $\forall i$.

Fig. 7 illustrates the algorithm delay under OCA and under ECA, when the total computation workload $w$ of the algorithm varies. We can see that the delay under OCA is always no greater than that under ECA, which demonstrates the better performance of OCA. We can also see that the delay is non-decreasing with $w$, which is because a larger workload takes more time to complete. We note that the performance gap is 0 when $w$ is small. This is because in this case, all the workloads can be completed before the last forward communication ends or after the first backward communication starts, such that the delay is equal to the total time of forward and backward communications, which is the same for both allocations. We further observe that the performance gain of OCA compared to ECA for diverse communication delays and computation rates (DMDC) is more than that for uniform communication delays and diverse computation rates (UMDC), or for diverse communication delays and uniform computation rates (DMUC). This is because when communication delays or computation rates are diverse rather than uniform, OCA is more different from ECA, so that OCA is more beneficial.

To illustrate the efficiency of the optimal communication scheduling order, we compare the algorithm delay under the optimal order given by Propositions 2 or 3, or the approximate optimal order found by Algorithm 2, and under an arbitrary order that schedules communications in the ascending order of users’ indices.

Fig. 7 illustrates the algorithm delay under the (approximate) optimal communication order (OCO) and under the arbitrary communication order (ACO), as the the total computation workload $w$ of the algorithm varies. As expected, we can see that OCO always outperforms ACO, and the delay is non-decreasing with $w$. Similar to Fig. 7, we note that the performance gap is 0 when $w$ is small, which is because in this case the delay is equal to the total delay of communications, which is the same for both scheduling orders. We can also observe that the performance gain of OCO compared to ACO for DMDC is more than that for UMDC or DMUC. Similar to Fig. 7, the reason is that when communication delays or computation rates are diverse rather than uniform, OCO is more different from ECA and thus is more beneficial.

To illustrate the impact of the selection of nodes, we compare the algorithm delay as the number of nodes selected for executing the algorithm varies. Fig. 7 illustrates the algorithm delay under the optimal computation allocation (OCA), under the (approximate) optimal communication order (OCO), and under both (OCA-OCO), as the number of selected nodes $N$ varies. We can see that the delay first decreases and then increases with $N$. This is because the delay reduction due to the computation workload completed by an additional node first outweighs the delay increase due to the communications of that node, and then the former effect is dominated by the second effect. We can also observe that the delay under OCA-OCO is better than under OCA or OCO only, which demonstrates that both OCA and OCO are beneficial.

Next we present counterexamples where the communication scheduling orders given by the largest delay first (LDF) policy and the fastest computing node last (FCL) policy are arbitrarily worse than the optimal orders, for the case of diverse computation rates and diverse communication delays.

First consider a setting where the delays of the communications are in the order $t_{1}\geq t_{2}\geq\cdots\geq t_{N-1}\geq t_{N}$, such that the LDF policy results in the order $(1,2,\cdots,N-1,N)$. Then the maximum computation workload that can be completed under this scheduling order is given by

However, the optimal scheduling order can be in the form of $(2,3,\cdots,N-1,N,1)$, such that the maximum workload is given by

if $r_{1}$ is sufficiently large. Furthermore, we can see that if $r_{1}\rightarrow\infty$, we have $w/w^{*}\rightarrow 0$, which means that the solution $w$ given by the LDF policy can be arbitrarily worse than the optimal solution $w^{*}$. This is because LDF ignores the computation rates $\{r_{i}\}$ in determining the scheduling order, so that the maximum workload $w$ is independent of the computation rate $r_{1}$, which can be very large. Consider another example where the nodes’ computation rates are in the order $r_{1}\leq r_{2}\leq\cdots\leq r_{N-1}\leq r_{N}$, such that the FCL policy results in the order $(1,2,\cdots,N-1,N)$. Then the maximum computation workload that can be completed is also given by (1). However, the optimal scheduling order can also be $(2,3,\cdots,N-1,N,1)$, such that the maximum workload is also given by (2), if $t_{N}$ is sufficiently large. Then we can see that if $t_{N}\rightarrow\infty$, we have $w/w^{*}\rightarrow 0$, which means that the solution $w$ given by FCL can be arbitrarily worse than the optimal solution $w^{*}$. This is because FCL ignores the communication delays $\{s_{i}\}$ in determining the scheduling order, so that the maximum workload $w$ is independent of the communication delay $t_{N}$, which can be very large.

The main idea of the proof is an exchange argument. WLOG, suppose forward communication M1 is interrupted by forward communication M2 into two parts, such that the 2nd part of M1 starts after M2 (or part of M2) is completed, as illustrated in Fig. 8 (a). If M1 is interrupted for multiple times, the proof follows by applying the exchange argument multiple times. Now we exchange the scheduling order of the 1st part of M1 and M2 (or the interrupting part of M2), as illustrated in Fig. 8 (b). We can see that the order exchange does not affect the schedules of computations C1 and C2, as well as the schedule of any communication or computation on the nodes other than nodes 1 and 2. As a result, the delay of the algorithm remain the same. This completes the proof.

The main idea of the proof is an exchange argument. According to Lemma 1, it suffices to focus on non-preemptive scheduling. WLOG, suppose forward communication FM1 is scheduled after backward communication BM2, as illustrated in Fig. 9 (a). Now we exchange the scheduling order of FM1 and BM2, as illustrated in Fig. 9 (b). We can see that the order exchange does not affect the schedules of computations C1 and C2, as well as the schedule of any communication or computation on the nodes other than nodes 1 and 2. As a result, the delay of the algorithm remain the same. This completes the proof.

The main idea of the proof is a shifting argument. According to Lemma 1 and Lemma 2, it suffices to focus on non-preemptive scheduling policies that schedule all forward communications before all backward communications. WLOG, suppose there is an idle period of the wireless network between forward communication M1 and forward communication M2, as illustrated in Fig. 10 (a). If there are multiple idle periods, the proof follows by applying the exchange argument multiple times. Now we shift M2 to be right after M1, as illustrated in Fig. 10 (b). We can see that the shifting does not affect the schedules of computations C1 and C2, as well as the schedule of any communication or computation on the nodes other than nodes 1 and 2. As a result, the delay of the algorithm remain the same. If M1 and M2 are backward communications, we can shift M1 to be right before M2, and the same argument applies. This completes the proof.

The main idea of the proof is a shifting argument. We first note that a lower bound of the algorithm delay is the total delay $D$ of all forward and backward communications. Therefore, if Algorithm 1 terminates in Phase 1 or Phase 2, then it finds a feasible schedule of all the computation workloads of the algorithm, such that the algorithm delay is equal to $D$. Suppose the Algorithm 1 terminates in Phase 3, and the remaining total unallocated computation workloads is not allocated to the nodes in proportional to their computation rates. Then there must be some node that is idle for some period after all forward communications and before all backward communications, as illustrated in Fig. 11 (a). In this case, we can always shift some workload from some other node to this node without increasing the algorithm delay, until there is no such idle period, as illustrated in Fig. 11 (b). This completes the proof.

Let $o$ be the scheduling order found by Algorithm 2 such that the communication of node $o(i)$ is scheduled at the $i$th in the order. Let $o^{*}$ be the optimal scheduling order. For convenience, define

Also define $v\triangleq\sum^{N}_{i=1}f_{i}$ and $v^{*}\triangleq\sum^{N}_{i=1}f^{*}_{i}$. Let $o_{k}$ be an ascending order of $k$ elements in $\mathcal{N}$. For any $o^{*}$ and $o_{k}$, we construct a new order $o^{\prime}$ of the elements in $\mathcal{N}$ such that $o^{\prime}(i)=o^{*}(o_{k}(i))$, $\forall i\in\{1,\cdots,k\}$ (the elements $o^{\prime}(i)$, $\forall i\in\{k+1,\cdots,N\}$ can be arbitrary, so there can be multiple such $o^{\prime}$). Intuitively, we move the $k$ elements of $o^{*}$ with order indices given by $o_{k}$ to be the first $k$ elements in $o^{\prime}$, while keeping the relative order of these $k$ elements the same. For example, if $o^{*}=(5,4,3,2,1)$ and $o_{k}=(1,3,5)$ with $k=3$, then $o^{\prime}=(5,3,1,4,2)$. Define

Then we have

where the inequality is due to that

is a subset of

To see this, for the previous example, if $i=2$, we have

Then we have

for any $o_{k}$, where the 1st inequality is due to Algorithm 2, and the 2nd inequality is due to (Proof of Proposition 4). Using the above we have

where the 2nd equality is due to that we sum up $\sum^{k}_{i=1}f^{*}_{o_{k}(i)}$ for all possible orders of $o_{k}$ whose number is ${N\choose k}$. Thus we have $v/v^{*}\geq k/N$. This completes the proof.