Remarks on dynamic load balancing of integer loads and integral graphs

Abstract

Cvetković et al. (2010) [3] presented an algorithm for dynamic load balancing in discrete load model based on the eigenvectors of the adjacency matrix of the processor network. In case of integral graphs, whose eigenvalues are integers and whose eigenvector basis may be chosen to consist of integers only, this algorithm executes in integer arithmetic, providing an argument for the use of integral graphs as suitable candidates for processor networks. It is observed here that this algorithm, however, is not capable of balancing all integer load distributions. After specifying a necessary and sufficient condition for properly managing all integer load distributions, it becomes apparent that the proposed algorithm does not actually depend on the integrality of eigenvectors, but on employing a set of balancing flows carrying a unit load from a fixed vertex to each of the remaining vertices in the graph. Such sets exist for every connected graph and, thus, yield a simple load balancing algorithm that can be executed in integer arithmetic for every processor network.