Parallel computing as a congestion game

Abstract

Game-theoretical approach to the analysis of parallel algorithms is proposed. The approach is based on presentation of the parallel computing as a congestion game. In the game processes compete for resources such as core of a central processing unit and a communication subsystem. There are players, resources and payoffs (time delays) of players which depend on resources usage. Comparative analysis of various optimality principles in the proposed model may be performed.