- 50 views
- 54 downloads
On Resource Allocation in Time-constrained Coded Distributed Computing Systems
-
- Author / Creator
- Mehrabi, Mehrad
-
Distributed computing systems have been widely used in recent years to handle massive computations required by newly emerged machine learning algorithms and signal processing problems. Also, the use of error correction codes has been proposed to mitigate the negative impact of slow workers by adding redundancy to the computational tasks. In practice, a distributed computing system often receives multiple tasks each needs to be finished by a specific deadline. Furthermore, service providers may offer different levels of service based on their users' subscription tiers. In this thesis, we first consider a scenario where multiple matrix-vector multiplication jobs arrive in a distributed computing system. The main challenges in such a system are random task arrivals and random execution times due to the slow workers. To address these challenges, we present two algorithms to maximize the number of tasks completed before their deadlines. Then, we study a tiered time-constrained distributed computing system, where there are multiple users with distinct subscription classes and each with a time-sensitive computational job. We assume the system receives rewards for finishing tasks prior to their deadlines and gives higher priority to tasks associated with higher subscription tiers. To maximize the overall reward of the system, we present a worker assignment scheme. In both studies, it is shown that our proposed algorithms provide comparable performances to unachievable upper bounds while exhibiting significantly lower complexity.
-
- Subjects / Keywords
-
- Graduation date
- Fall 2023
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.