Quasirandom Load Balancing

摘要: We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The is completely deterministic, though it tries to imitate (and enhance) randomized by keeping the accumulated rounding errors as small possible. Our new algorithm, surprisingly, closely approximates idealized process (where are divisible) important network topologies. On $d$-dimensional torus graphs with $n$ nodes deviates from only an additive constant. In contrast, approach of Friedrich and Sauerwald [Proceedings \textup41st Annual ACM Symposium Theory Computing, 2009, pp. 121--130] can deviate up $\Omega(\operatorname{polylog}(n))$, deterministic Rabani, Sinclair, Wanka \textup39th IEEE Foundations Computer Science, 1998, 694--705] has deviation $\Omega(n^{1/d})$. This makes our quasirandom first known t...