MDS coding is better than replication for job completion times

Ken R. Duffy; Vsevolod Shneer

doi:10.1016/j.orl.2020.11.010

MDS coding is better than replication for job completion times

Ken R. Duffy, Vsevolod Shneer

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

28 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 language	English
Pages (from-to)	91-95
Number of pages	5
Journal	Operations Research Letters
Volume	49
Issue number	1
Early online date	19 Nov 2020
DOIs	https://doi.org/10.1016/j.orl.2020.11.010
Publication status	Published - 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

Access to Document

10.1016/j.orl.2020.11.010

Download pdf
© 2020 Elsevier B.V.
Accepted author manuscript, 241 KBLicence: CC BY-NC-ND

Cite this

@article{706b5f3b7f964a73ba1ac3c892312f81,

title = "MDS coding is better than replication for job completion times",

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.",

keywords = "Batch-completion times, Load balancing, MDS codes, Replication",

author = "Duffy, {Ken R.} and Vsevolod Shneer",

note = "Funding Information: This publication has emanated from research conducted with the financial support of Science Foundation Ireland under Grant number 18/CRT/6049 . The opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Science Foundation Ireland. Publisher Copyright: {\textcopyright} 2020 Elsevier B.V. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

year = "2021",

month = jan,

doi = "10.1016/j.orl.2020.11.010",

language = "English",

volume = "49",

pages = "91--95",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - MDS coding is better than replication for job completion times

AU - Duffy, Ken R.

AU - Shneer, Vsevolod

N1 - Funding Information: This publication has emanated from research conducted with the financial support of Science Foundation Ireland under Grant number 18/CRT/6049 . The opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Science Foundation Ireland. Publisher Copyright: © 2020 Elsevier B.V. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2021/1

Y1 - 2021/1

N2 - 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.

AB - 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.

KW - Batch-completion times

KW - Load balancing

KW - MDS codes

KW - Replication

UR - http://www.scopus.com/inward/record.url?scp=85097142897&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2020.11.010

DO - 10.1016/j.orl.2020.11.010

M3 - Article

SN - 0167-6377

VL - 49

SP - 91

EP - 95

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

MDS coding is better than replication for job completion times

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this