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

Atsushi SASAKI

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A    No.6    pp.1573-1582
Publication Date: 2005/06/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.6.1573
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
distributed algorithm,  task assignment,  resource allocation,  fairness,  unidirectional ring,  

Full Text: PDF>>
Buy this Article


Summary: 
This paper presents a distributed task assignment 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. This time period is almost optimal for a unidirectional ring. The FCFS policy is very important in terms of task fairness and can also avoid starvation and provide an efficient response time. Simulation results show that the algorithm generally works better than conventional task assignment or load balancing schemes with respect to both mean response time and task fairness.