In this paper, we explore distributed edge computation offloading (DECO) that offloads computation to distributed edge devices connected wirelessly, which perform the offloaded computation in parallel. By integrating edge computing with parallel computing, DECO can substantially reduce the total computation delay. In particular, we study the fundamental problem of minimizing the total completion time of DECO. We show that the time-sharing based communication resource allocation always outperforms the bandwidth-sharing scheme, so that it suffices to focus on the time-sharing based communication scheduling. Based on the time-sharing scheme, we first establish some structural properties of the optimal communication scheduling policy. Then, given these properties, we develop an efficient algorithm that finds the optimal allocation of computation workloads. Next, based on the optimal computation allocation, we characterize the optimal scheduling order of communications, which exhibits an elegant structure: the optimal order is in the non-decreasing order of the ratio between a device’s computation rate and its communication time. Last, based on the optimal computation allocation and communication scheduling, we show that the optimal device selection problem is a submodular minimization problem, so that it can be solved efficiently using some existing methods. We further extend the study to the setting where devices are subject to maximum computation workload constraints, and develop an efficient algorithm that finds the optimal computation workload allocation. Our results provide useful insights for the optimal computation-communication co-design for DECO. We evaluate the theoretical findings using extensive simulations in both practical settings and controlled settings, which demonstrate the performance of DECO in practice and also the efficiency of our proposed schemes and algorithms for DECO.

Distributed edge computation offloading makes use of distributed wireless edge devices to perform offloaded computation in parallel, which can substantially reduce the computation time. In this article, we explore distributed edge computation offloading where the computation workloads of edge devices are correlated with their communication workloads. In particular, we study the fundamental problem of computation workload allocation and communication scheduling for minimizing the total completion time of the computation offloading. To solve this problem, we need to tackle several challenges due to the precedence constraints of computations and communications, the interference constraints of wireless edge devices, and the correlation between computation and communication workloads. We consider preemptive, half-preemptive, and non-preemptive networks for the formulated problem, respectively. For each setting, we first develop a simplified problem of computation allocation, based on which we then devise an efficient and feasible policy that can arbitrarily approach the optimal policy. For half-preemptive and non-preemptive networks, we also characterize the optimal communication orders. Our results provides useful insights for the computation-communication co-design of distributed edge computation offloading. We evaluate the proposed algorithms using simulation results, which corroborate the advantages of the algorithms.