Theory Lunch

TIME:: *Tuesday*, Sept. 4, noon till 1pm

PLACE:: 4623 Wean Hall

TITLE::  Task Assignment with Unknown Duration

SPEAKER::  Mor Harchol-Balter

INTENDED AUDIENCE:: New graduate students, particularly those with
theoretical interests. This talk does not assume any background.


To build high-capacity server systems, developers are increasingly
turning to distributed designs (e.g.  distributed Web servers,
distributed database servers, and high performance computing
clusters).  In distributed servers, tasks arrive and must be assigned
to one of the host machines for processing.  Fundamental to designing
any of these systems is the process of choosing a "task assignment
policy", namely a rule for assigning tasks to host machines.  The
question of which task assignment policy is ``best'' (minimizes mean
response time) is an age-old question which still remains open for
many models.

Our particular model is motivated by supercomputing systems: jobs are
not preemptible and the job'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 the performance of several natural
task assignment policies and propose a new one, called TAGS.  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.