MDS coding is better than replication for job completion times

Ken R. Duffy, Vsevolod Shneer

Research output: Contribution to journalArticlepeer-review

4 Downloads (Pure)

Abstract

If queue-states are unknown to a dispatcher, a replication strategy has been proposed where job copies are sent randomly to servers. When the service of any copy is completed, redundant copies are removed. For jobs that can be algebraically manipulated and have linear servers, to get the response-time performance of sending d copies of n jobs via the replication strategy, with Maximum Distance Separable (MDS) codes we show that n+d jobs suffice. That is, while replication is multiplicative, MDS is linear.

Original languageEnglish
Pages (from-to)91-95
Number of pages5
JournalOperations Research Letters
Volume49
Issue number1
Early online date19 Nov 2020
DOIs
Publication statusPublished - Jan 2021

Keywords

  • Batch-completion times
  • Load balancing
  • MDS codes
  • Replication

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'MDS coding is better than replication for job completion times'. Together they form a unique fingerprint.

Cite this