Speaker
Ms
Natalia Nikitina
(Institute of Applied Mathematical Research, Karelian Research Center RAS)
Description
In many applied scientific problems, diversity of the results set is no less important than their amount. An example of such problem is the virtual drug screening. According to the principles of drug development, the structural diversity is one of the key characteristics of the resulting molecules set. At the same time, virtual drug screening is a time- and resource-consuming computational problem that requires high-performance computing resources in order to be solved. This work aims to develop a task scheduling algorithm which allows to obtain the results set of the largest possible size and diversity in the shortest time. In particular, we consider Desktop Grid systems that are widely used for virtual screening. In such systems task scheduling is complicated by the heterogeneity of computational nodes and the ability of separate nodes to join and leave Desktop Grid in random times. So, the computing nodes are considered as independent agents. To model task scheduling process in a Desktop Grid we use a congestion game. Congestion games describe situations where players compete for using a shared set of resources, and the utility of each player depends not only on the chosen resource, but also on the number of other players using it ("congestion level"). The game considered in the work is proven to have at least one Nash equilibrium in pure strategies. The equilibrium situation means that no node can increase amount of its useful work by unilaterally deviating from the schedule. Moreover, best-and better-response dynamics are guaranteed to converge to equilibrium in polynomial time.
Summary
Diversity of results is an important issue in many applied problems including virtual drug screening. We propose a game-theoretical model of task scheduling that allows to minimize the time to obtain large and diverse set of results considering limited knowledge about the input dataset structure. The model is of special importance for Desktop Grids which have heterogeneous and unstable environment.
Primary authors
Mr
Evgeny Ivashko
(Institute of Applied Mathematical Research of RAS)
Ms
Natalia Nikitina
(Institute of Applied Mathematical Research, Karelian Research Center RAS)
