20th IEEE International Conference on Distributed Computing Systems (ICDCS'00)
Task Assignment with Unknown Duration
Taipei, Taiwan
April 10-April 13
ISBN: 0-7695-0601-1
We consider a distributed server system and ask which policy should be used for assigning tasks to hosts. In our server, tasks are not preemptible. In addition, the task's service demand is not known a priori. We are particularly concerned with the case where the workload is heavy-tailed, as is characteristic of many empirically measured computer workloads. We analyze several natural task assignment policies and propose a new one TAGS (Task Assignment based on Guessing Size).The TAGS algorithm is counterintuitive in many respects, including load unbalancing, non-work-conserving, and fairness. We find that under heavy-tailed workloads, TAGS can outperform all task assignment policies known to us by several orders of magnitude with respect to both mean response time and mean slowdown, provided the system load is not too high.