Incentive-Based Coded Distributed Computing Management for Latency Reduction in IoT Services—A Game Theoretic Approach
Nakyoung Kim, Daejin Kim, Joohyung Lee, Dusit Niyato, Jun Kyun Choi
Abstract
This article studies distributed computing (DC) mechanisms on heterogeneous mobile devices (MDs) for latency reduction (LR) in Internet-of-Things (IoT) services by mitigating the effect of straggling MDs. We propose novel coded DC mechanisms with two different incentive distributions that consider the time-discounting value of processed results and the amount of the workload computed by MDs. Specifically, we consider distributed gradient descent computing with coding when a task publisher (TP) with a limited amount of budget offers incentives to encourage MDs' participation in the computation. To analyze a hierarchical decision-making structure of the TP and MDs, we formulate a strategic competition between them as a Stackelberg game. In the case that the MDs are the leaders, we design a CPU-cycle frequency control scheme to balance each MD's computing speed and energy consumption for obtaining its maximum utility with the incentive mechanisms. As the follower, the TP aims at minimizing latency of the DC, and it follows the MDs' decisions to determine the load allocation for each MD. Then, we design an algorithm achieving the Stackelberg equilibrium, which is shown to be a unique Nash equilibrium of the game. The performance evaluation results show that the proposed mechanisms achieve 39% of LR on average compared to the benchmark mechanism. Furthermore, the results corroborate the efficiency of the proposed mechanisms in terms of the MDs' social welfare.