Sparse Token Distribution on Reconfigurable Meshes


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.

[Up to Computer Science Technical Report Archive: Home Page]