Author: Gavin Turner
Source: GZipped PostScript (68kb); Adobe PDF
(329kb)
We propose and analyse an algorithm to optimally solve the Token Distribution problem, a static variant of the load balancing problem, on the ring and linear-array. The algorithm has the added benefit that it is a dimension exchange algorithm. Dimension exchange algorithms use a colouring of the interconnection network to pair procesors for data exchange, are extremely simple, and totally scalable.