Authors: Heiko Schr\"oder, Gavin Turner
Source: GZipped PostScript (70kb); Adobe PDF
(353kb)
A solution to the k-sparse token distribution problem is presented for the 2-dimensional reconfigurable mesh. The algorithm, being the first algorithm proposed to solve this problem under any model of reconfiguration, is shown to be asymptotically worst-case optimal in reducing the discrepancy between maximum and minimum processor loads by 1 in optimal O(\sqrt{k}) time steps. In addition, the algorithm provides an optimal solution to more general (non-sparse) token distribution problems.