Scientific publications

This paper investigates a game-theoretic mathematical model of task scheduling in a computational system with linear externalities. Each player aims to maximize their performance in the presence of positive externalities. The proposed model describes task scheduling in a volunteer computing system of Desktop Grid type, while the externalities express the information exchange in the process of solving a scientific problem. Desktop Grid systems employ computational capacities of nondedicated computers that are united by a data transmission network and perform computations in their idle time. In such systems, a computationally intensive scientific problem is often divided into several interconnected subproblems to be performed in parallel. The intermediate results of solving one subproblem can aid in solving other subproblems by optimizing or reducing the computations. Proof is provided that the game is a potential game in cases of homogeneous processors or tasks and equal externalities, invariant or symmetric externalities. In the cases with homogeneous processors or tasks and equal externalities or invariant externalities, the Nash equilibrium is unique and globally optimal, while the case with symmetric externalities allows multiple Nash equilibriums in pure strategies. We present the results of computational experiments modeling task scheduling using the proposed method in comparison with a number of popular algorithms. The provided results expand the applicability of classical models, proving the existence of an equilibrium and convergence to it in both delay minimization and performance maximization problems. The potential function form found here facilitates the use of global optimization methods to search for equilibriums.