Delta probing policies for redundancy

We consider job dispatching in systems with N parallel servers, where jobs arrive according to a Poisson process of rate λ. In redundancy-d policies, replicas of an arriving job are assigned to d ≤ N servers selected uniformly at random (without replacement) with the objective to reduce the delay. We introduce a quite general workload model, in which job sizes have some probability distribution while the speeds (slowdown factors) of the various servers for a given job are allowed to be inter-dependent and non-identically distributed. This allows not only for inherent speed differences among different servers, but also for affinity relations. We further propose two novel redundancy policies, so-called delta-probe-d policies, where d probes of a fixed, small, size ∆ are created for each incoming job, and assigned to d servers selected uniformly at random. As soon as the first of these d probe tasks finishes, the actual job is assigned for execution – with the same speed – to the corresponding server and the other probe tasks are abandoned. We also consider a delta-probe-d policy in which the probes receive preemptive-resume priority over regular jobs. The aim of these policies is to retain the benefits of redundancy-d policies while accounting for systematic speed differences and mitigating the risks of running replicas of the full job simultaneously for long periods of time.