Optimal parameters for load balancing using the diffusion method in \(k\)- ary \(n\)-cube network (Q689618)

The diffusion method is a simple but practical method for dynamic load balancing in distributed memory message-passing multiprocessors. It is iterative in nature and is fully distributed. Its efficiency depends on a parameter, the diffusion parameter, which dictates how excess workloads are to be diffused away. We derive optimal values for this parameter for the cases of the \(k\)-ary \(n\)-cube and its variant, the \(n\)-dimensional torus. With these optimal paarameters, the diffusion method is guaranteed to terminate at a balanced state in optimal time.