% Encoding: UTF-8
@COMMENT{BibTeX export based on data in FAU CRIS: https://cris.fau.de/}
@COMMENT{For any questions please write to cris-support@fau.de}
@article{faucris.118435284,
abstract = {The token distribution (TD) problem, an abstract static variant of load balancing, is defined as follows: let M be a (parallel processor) network with set P of processors. Initially, each processor P ∈ P has a certain amount l(P) of tokens. The goal of a TD algorithm, run on M, is to distribute the tokens evenly among the processors. In this paper we introduce the notion of strongly adaptive TD algorithms, i.e., algorithms whose running times come close to the best possible runtime, the off-line complexity of the TD problem, for each individual initial token distribution l. Until now, only weakly adaptive algorithms have been considered, where the running time is measured in terms of the maximum initial load max{l(P)|P ∈ P}. We design an almost optimal, strongly adaptive algorithm on mesh-connected networks of arbitrary dimension extended by a single 1-bit bus. This result shows that an on-line TD algorithm can come close to the optimal (off-line) bound for each individual initial load. Furthermore, we exactly characterize the off-line complexity of arbitrary initial token distributions on arbitrary networks. As an intermediate result, we design almost optimal weakly adaptive algorithms for TD on mesh-connected networks of arbitrary dimension.},
author = {Wanka, Rolf and et al.},
author_hint = {Meyer auf der Heide F, Oesterdiekhoff B, Wanka R},
doi = {10.1007/BF01955042},
faupublication = {no},
journal = {Algorithmica},
keywords = {Parallel algorithms; Token distribution},
pages = {413-427},
peerreviewed = {Yes},
support_note = {Author relations incomplete. You may find additional data in field 'author{\_}hint'},
title = {{Strongly} {Adaptive} {Token} {Distribution}},
volume = {15},
year = {1996}
}