  We analyze the performance of redundancy in a multi-type job and multi-type
server system. We assume the job dispatcher is unaware of the servers'
capacities, and we set out to study under which circumstances redundancy
improves the performance. With redundancy an arriving job dispatches redundant
copies to all its compatible servers, and departs as soon as one of its copies
completes service. As a benchmark comparison, we take the non-redundant system
in which a job arrival is routed to only one randomly selected compatible
server. Service times are generally distributed and all copies of a job are
identical, i.e., have the same service requirement. In our first main result,
we characterize the sufficient and necessary stability conditions of the
redundancy system. This condition coincides with that of a system where each
job type only dispatches copies into its least-loaded servers, and those copies
need to be fully served. In our second result, we compare the stability regions
of the system under redundancy to that of no redundancy. We show that if the
server's capacities are sufficiently heterogeneous, the stability region under
redundancy can be much larger than that without redundancy. We apply the
general solution to particular classes of systems, including redundancy-d and
nested models, to derive simple conditions on the degree of heterogeneity
required for redundancy to improve the stability. As such, our result is the
first in showing that redundancy can improve the stability and hence
performance of a system when copies are non-i.i.d..
