For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Distributed Task Assignment Algorithm with the FCFS Policy in a Logical Ring
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/06/01
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
distributed algorithm, task assignment, resource allocation, fairness, unidirectional ring,
Full Text: PDF(279.7KB)>>
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.