  As job redundancy has been recognized as an effective means to improve
performance of large-scale computer systems, queueing systems with redundancy
have been studied by various authors. Existing results include methods to
compute the queue length distribution and response time but only when the
service discipline is First-Come-First-Served (FCFS). For other service
disciplines, such as Processor Sharing (PS), or Last-Come-First-Served (LCFS),
only the stability conditions are known. In this paper we develop the first
methods to approximate the queue length distribution in a queueing system with
redundancy under various service disciplines. We focus on a system with
exponential job sizes, i.i.d. copies, and a large number of servers. We first
derive a mean field approximation that is independent of the scheduling policy.
In order to study the impact of service discipline, we then derive refinements
of this approximation to specific scheduling policies. In the case of Processor
Sharing, we provide a pair and a triplet approximation. The pair approximation
can be regarded as a refinement of the classic mean field approximation and
takes the service discipline into account, while the triplet approximation
further refines the pair approximation. We also develop a pair approximation
for three other service disciplines: First-Come-First-Served, Limited Processor
Sharing and Last-Come-First-Served. We present numerical evidence that shows
that all the approximations presented in the paper are highly accurate, but
that none of them are asymptotically exact (as the number of servers goes to
infinity). This makes these approximations suitable to study the impact of the
service discipline on the queue length distribution. Our results show that FCFS
yields the shortest queue length, and that the differences are more substantial
at higher loads.
