  Redundancy-d (R(d)) is a load balancing method used to route incoming jobs to
K servers, each with its own queue. Every arriving job is replicated into
2<=d<=K tasks, which are then routed to d servers chosen uniformly at random.
When the first task finishes service, the remaining d-1 tasks are cancelled and
the job departs the system.
  Despite the fact that R(d) is known, under certain conditions, to
substantially improve job completion times compared to not using redundancy at
all, little is known on a more fundamental performance criterion: what is the
set of arrival rates under which the R(d) queueing system with FIFO service
discipline is stable? In this context, due to the complex dynamics of systems
with redundancy and cancellations, existing results are scarce and are limited
to very special cases with respect to the joint service time distribution of
tasks.
  In this paper we provide a non-trivial, closed form lower bound on the
stability region of R(d) for a general joint service time distribution of tasks
with finite first and second moments. We consider a discrete time system with
Bernoulli arrivals and assume that jobs are processed by their order of
arrival. We use the workload processes and a quadratic Lyapunov function to
characterize the set of arrival rates for which the system is stable. While
simulation results indicate our bound is not tight, it provides an
easy-to-check performance guarantee.
