非表示:
キーワード:
-
要旨:
Deterministic and randomized balancing schemes are used to distribute workload
evenly in networks. In this paper, we compare two very general ones: The random
walk and the (deterministic) Propp machine. Roughly speaking, we show that on
the two-dimensional grid, the Propp machine always has the same number of
tokens on a node as does the random walk in expectation, apart from an additive
error of less than eight. This constant is independent of the total number of
tokens and the runtime of the two processes. However, we also show that it
makes a difference whether the Propp machine serves the neighbors in a circular
or non-circular order.
