STRONGLY ADAPTIVE TOKEN DISTRIBUTION

The token distribution (TD) problem, an abstract static variant of loa d balancing, is defined as follows: let M be a (parallel processor) ne twork with set P of processors. Initially, each processor P is an elem ent of P has a certain amount l(P) of tokens. The goal of a TD algorit hm, run on M, is to distribute the tokens evenly among the processors. In this paper we introduce the notion of strongly adaptive TD algorit hms, i.e., algorithms whose running times come close to the best possi ble runtime, the off-line complexity of the TD problem, for each indiv idual initial token distribution l. Until now, only weakly adaptive al gorithms have been considered, where the running time is measured in t erms of the maximum initial load max{l(P)\P is an element of P}. We de sign an almost optimal, strongly adaptive algorithm on mesh-connected networks of arbitrary dimension extended by a single 1-bit bus. This r esult shows that anon-line TD algorithm can come close to the optimal (off-line) bound for each individual initial load. Furthermore, we exa ctly characterize the off-line complexity of arbitrary initial token d istributions on arbitrary networks. As an intermediate result, we desi gn almost optimal weakly adaptive algorithms for TD on mesh-connected networks of arbitrary dimension.