Delta probing policies for redundancy

Research output: Contribution to journalConference articlepeer-review

1 Citation (Scopus)
1 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)72-73
Number of pages2
JournalPerformance Evaluation Review
Volume46
Issue number3
DOIs
Publication statusPublished - 25 Jan 2019
Event36th IFIP Performance Conference 2018 - Toulouse, France
Duration: 5 Dec 20187 Dec 2018

Keywords

  • Delay performance
  • Dispatching
  • Parallel-server system
  • Probing policies
  • Redundancy

Fingerprint Dive into the research topics of 'Delta probing policies for redundancy'. Together they form a unique fingerprint.

Cite this