Nearest Neighbor Task Allocation for Large-Scale Distributed Systems

In this paper, we consider distributed task allocation in distributed systems. In order to improve the performance, using load information of nodes is promising. In reality, however, it is common that load information is not up to date when it is used. Load information may be updated only periodically, or the communication delay for a task to move to other node makes load information out of date. The performance of task allocation schemes is significantly damaged if the load information is old. In order to tackle this problem, we introduce the nearest neighbor approach which is originally proposed for parallel computing. Restricting the communication to between neighboring nodes, the effect of communication delay is suppressed. Simulation results showed that our proposed scheme suppresses the effect of old load information and shows better performance than a previously proposed scheme.