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 -