  We investigate the stability condition of redundancy-$d$ multi-server
systems. Each server has its own queue and implements popular scheduling
disciplines such as First-Come-First-Serve (FCFS), Processor Sharing (PS), and
Random Order of Service (ROS). New jobs arrive according to a Poisson process
and copies of each job are sent to $d$ servers chosen uniformly at random. The
service times of jobs are assumed to be exponentially distributed. A job
departs as soon as one of its copies finishes service. Under the assumption
that all $d$ copies are i.i.d., we show that for PS and ROS (for FCFS it is
already known) sending redundant copies does not reduce the stability region.
Under the assumption that the $d$ copies are identical, we show that (i) ROS
does not reduce the stability region, (ii) FCFS reduces the stability region,
which can be characterized through an associated saturated system, and (iii) PS
severely reduces the stability region, which coincides with the system where
all copies have to be \emph{fully} served. The proofs are based on careful
characterizations of scaling limits of the underlying stochastic process.
Through simulations we obtain interesting insights on the system's performance
for non-exponential service time distributions and heterogeneous server speeds.
