A Distributed Task Assignment Algorithm with the FCFS Policy in a Ring

A. Sasaki (Japan)


: distributed algorithm, task assignment, re source allocation, fairness, unidirectional ring


This paper presents a distributed task as signment algorithm in a (logical) unidirectional ring, which guarantees that almost all tasks are assigned to servers with the first come first served (FCFS) policy without a global clock. A task assignment for a process is obtained in the time period needed for a message to circle the ring. The time is almost optimal. The FCFS policy is very impor tant in terms of task fairness and can also avoid starvation and provide an efficient response time. A simulation result shows that the algorithm generally works better than con ventional task assignment or load balancing schemes with respect to both mean response time and task fairness.

Important Links:

Go Back