Multi-agent local voting protocol for online DAG scheduling

Zhitnukhin N.A., Zhadan A.Y., Kondratov I.V., Allahverdyan A.L., Granichin O.N., Petrosian O.L., Romanovskii A.V., Kharin V.S.
 pdf (1617K)

Scheduling computational workflows represented by directed acyclic graphs (DAGs) is crucial in many areas of computer science, such as cloud/edge tasks with distributed workloads and data mining. The complexity of online DAG scheduling is compounded by the large number of computational nodes, data transfer delays, heterogeneity (by type and processing power) of executors, precedence constraints imposed by DAG, and the nonuniform arrival of tasks. This paper introduces the Multi-Agent Local Voting Protocol (MLVP), a novel approach focused on dynamic load balancing for DAG scheduling in heterogeneous computing environments, where executors are represented as agents. The MLVP employs a local voting protocol to achieve effective load distribution by formulating the problem as a differentiated consensus achievement. The algorithm calculates an aggregated DAG metric for each executor-node pair based on node dependencies, node availability, and executor performance. The balance of these metrics as a weighted sum is optimized using a genetic algorithm to assign tasks probabilistically, achieving efficient workload distribution via information sharing and reaching consensus among the executors across the system and thus improving makespan. The effectiveness of the MLVP is demonstrated through comparisons with the state-of-the-art DAG scheduling algorithm and popular heuristics such as DONF, FIFO, Min- Min, and Max-Min. Numerical simulations show that MLVP achieves makepsan improvements of up to 70% on specific graph topologies and an average makespan reduction of 23.99% over DONF (state-of-the-art DAG scheduling heuristic) across randomly generated diverse set of DAGs. Notably, the algorithm’s scalability is evidenced by enhanced performance with increasing numbers of executors and graph nodes.

Keywords: multi-agent, local voting protocol, scheduling, directed acyclic graph
Citation in English: Zhitnukhin N.A., Zhadan A.Y., Kondratov I.V., Allahverdyan A.L., Granichin O.N., Petrosian O.L., Romanovskii A.V., Kharin V.S. Multi-agent local voting protocol for online DAG scheduling // Computer Research and Modeling, 2025, vol. 17, no. 1, pp. 29-44
Citation in English: Zhitnukhin N.A., Zhadan A.Y., Kondratov I.V., Allahverdyan A.L., Granichin O.N., Petrosian O.L., Romanovskii A.V., Kharin V.S. Multi-agent local voting protocol for online DAG scheduling // Computer Research and Modeling, 2025, vol. 17, no. 1, pp. 29-44
DOI: 10.20537/2076-7633-2025-17-1-29-44
URL: http://crm-en.ics.org.ru/journal/article/3574/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2025 Institute of Computer Science