Distributed Convex Relaxation for Heterogeneous Task Replication in Mobile Edge Computing

Mobile edge computing (MEC) is expected to support real-time services at wireless networks, where task replication is applied to guarantee job completion within a strict deadline through replicating multiple copies to different edge servers. Most of previous works focused on guaranteeing the reliability of individual task in MEC-based networks with the assumption of homogeneous task execution distribution. Further, these algorithms cannot suit dynamic network scales, due to overhigh communication or retraining overhead. Therefore, this paper formulates the problem of heterogeneous task replication in a finer level by modeling outage probability of individual replication, where the decisions of all tasks are jointly optimized within the constraints of both mobile users and MEC servers for minimizing job outage probability. To adapt to varying network scales, we develop centralized and distributed algorithms, respectively. The centralized algorithm is developed based on Interior Point Method, which obtains the optimal solution of relaxed model and then approximates to the solution of original problem. Further, the distributed algorithm decomposes the HTR into multiple subproblems and parallelly compute each local solution based on Distributed ADMM. Finally, we build a simulation model and conduct comprehensive results, which demonstrates that the proposed algorithms can achieve high-accuracy solution with fast convergence.