Multiple-Task Coded Computing for Distributed Computation Framework: Modeling and Delay Analysis
- 25 March 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 72 (8) , 5032-5046
Abstract
Coded computing has received significant attention thanks to its advantage in alleviating the straggler effect in distributed computation framework, which would be one of the key fundamental techniques to enable the distributed and decentralized network architectures towards 5G-advanced and 6G era. Specifically, considering the scenario that multiple tasks randomly arrive at the network, the additional task queuing makes the delay analysis of coded computing more challenging. In this paper, we consider the impacts of task queuing and characterize the end-to-end delay for coded computing systems under the multi-task scenario. To this end, we first model the end-to-end coded computing system. Then, based on the redundant task processing strategies, we consider both purging and non-purging coded computing schemes. Although the expected end-to-end delay for both schemes are intractable, we obtain closed-form expressions for their respective lower and upper bounds, which generalizes the delay results of the single-task scenario. Moreover, we show that the multi-task coded computing has a coding gain of Θ(log n ) where n denotes the number of worker nodes, even with task queues considered. Simulation results verify the accuracy of the derived delay bounds and show the effectiveness of coded computing in the multi-task scenario.Keywords
This publication has 39 references indexed in Scilit:
- Vision, application scenarios, and key technology trends for 6G mobile communicationsScience China Information Sciences, 2022
- Towards 6G wireless communication networks: vision, enabling technologies, and new paradigm shiftsScience China Information Sciences, 2020
- Approximations and Bounds for (n, k) Fork-Join Queues: A Linear Transformation Approach2018
- Latency analysis of coded computation schemes over wireless networks2017
- Stochastic bounds in Fork–Join queueing systems under full and partial mappingQueueing Systems, 2016
- Coded MapReduce2015
- Performance Modeling and Design of Computer Systems2013
- Probability and Random Processes2001
- Tutorial on large deviations for the binomial distributionBulletin of Mathematical Biology, 1989
- The single server queue in heavy trafficMathematical Proceedings of the Cambridge Philosophical Society, 1961