Distributed Task Assignment Methods-A Dynamic Algorithm

摘要

We consider task assignment problem in distributed systems. Tasks are chosen by independent processing units (IPUs) which have only the knowledge of:1, their own situations; and 2, the system's simple feedbacks.We propose a dynamic algorithm with which IPUs can adjust their tasks in an adaptive fashion and in turn help the system getting optimal. This algorithm overcomes an important limitation of previous works, that is, the max reward probability r*≥0.5, and can get much better performance. Algorithm correctness is analyzed by Markov chains. Experiments and comparisons are presented.Reward/penalty dependency, an issue has not been addressed in previous works, is also analyzed. Moreover,this algorithm can also be used to solve the general assignment problem.