Result: Task Allocation in Distributed Computing Systems using Localized Distributed Algorithms

In this paper, we address the task allocation problem in a network of computational nodes, where each node is connected to a limited set of neighboring nodes. This issue is common in a variety of real-world distributed computing systems, such as edge, cloud, and grid computing. We have developed and compared five distinct local distributed task allocation (DTA) algorithms. These algorithms are termed “local” because they are designed to function in a distributed environment, where each node independently makes task allocation decisions. The decision-making process is based on simple rules that depend solely on locally available information from neighboring nodes. The goal of these algorithms is to achieve efficient task allocation without the need for a central controller, which is a key requirement in large-scale distributed systems today. Simulation results show that two algorithms, “local diffusion” (LD) and “local probabilistic” (LP), outperform the others in terms of performance metrics, with nearly identical results. However, in certain scenarios with a high task volume, LD slightly outperforms LP. When considering the algorithmic overhead, the LP algorithm is ultimately found to be the most efficient among all the tested algorithms.