The move-to-partner rule for self-organizing task allocation on a linear array
Walter J. Gutjahr · Stochastic Models · 2002
The well-known Move-to-Front rule for self-organizing lists is modified to a so-called Move-to-Partner rule for dynamic task allocation on a chain of processors. We enable an analysis of the sequence of expected communication costs by reducing their computation to that of three-dimensional arrays of certain probabilities, for which a recursion formula and an asymptotic expansion can be given. The costs depend on the underlying communication profile; two types of such profiles are investigated in more detail, namely a two-dimensional version of Zipf's law, and profiles based on a class structure of tasks. In the considered cases, the Move-to-Partner rule effects fast convergence to a stationary state, but comparably high expected stationary costs.