Affiliations: Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097 Warszawa, Poland. E-mail: chlebus@mimuw.edu.pl | Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097 Warszawa, Poland. E-mail: diks@mimuw.edu.pl | Département d'lnformatique Université du Québec à Hull Hull, Québec, J8X 3X7, Canada. E-mail: pelc@uqah.uquebec.ca
Abstract: There is given a graph, that models a communication network of a multiprocessor system, and there are tokens (jobs) allocated to nodes of the graph. The task is to distribute the tokens evenly, subject to the constraint that they may be moved only along the edges of the graph. The cost of a distribution strategy is measured as the total number of operations of moving a token along an edge. An algorithm for general graphs is developed, by reduction to a maximum-flow minimum-cost problem, that finds a cost-optimal distribution strategy, given a graph and an initial token allocation. The main result is an algorithm for graphs that are lines of nodes; it finds the distribution strategy in time O(n), for a line of n nodes.
Keywords: graph, token, optimal distribution, line of nodes
