We examine the question of whether to employ the
first-come-first-served (FCFS) discipline or the processor-sharing (PS)
discipline at the hosts in a distributed server system. We are
interested in the case in which service times are drawn from a
heavy-tailed distribution, and so have very high variability.
Traditional wisdom when task sizes are highly variable would prefer the
PS discipline, because it allows small tasks to avoid being delayed
behind large tasks in a queue. However, we show that system performance
can actually be significantly better under FCFS queueing, if each task
is assigned to a host based on the task's size. By task assignment, we
mean an algorithm that inspects incoming tasks and assigns them to hosts
for service. The particular task assignment policy we propose is called
SITA-E: Size Interval Task Assignment with Equal Load. Surprisingly,
under SITA-E, FCFS queueing typically outperforms the PS discipline by a
factor of about two, as measured by mean waiting time and mean slowdown
(waiting time of task divided by its service time). We compare the
FCFS/SITA-E policy to the processor-sharing case analytically; in
addition we compare it to a number of other policies in simulation. We
show that the benefits of SITA-E are present even in small-scale
distributed systems (four or more hosts). Furthermore, SITA-E is a
static policy that does not incorporate feedback knowledge of the state
of the hosts, which allows for a simple and scalable implementation.
<\H2>