TY - GEN
T1 - Deterministic random walks on the two-dimensional grid
AU - Doerr, Benjamin
AU - Friedrich, Tobias
PY - 2006/12/1
Y1 - 2006/12/1
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/77249105491
U2 - 10.1007/11940128_48
DO - 10.1007/11940128_48
M3 - Conference contribution
AN - SCOPUS:77249105491
SN - 3540496947
SN - 9783540496946
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 474
EP - 483
BT - Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings
T2 - 17th International Symposium on Algorithms and Computation, ISAAC 2006
Y2 - 18 December 2006 through 20 December 2006
ER -