TY - GEN
T1 - Fault-Tolerant Parallel Scheduling of Arbitrary Length Jobs on a Shared Channel
AU - Klonowski, Marek
AU - Kowalski, Dariusz R.
AU - Mirek, Jarosław
AU - Wong, Prudence W.H.
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - We study the problem of scheduling n jobs on m identical, fault-prone machines f of which are prone to crashes by an adversary, where communication takes place via a multiple access channel without collision detection. Performance is measured by the total number of available machine steps during the whole execution (work). Our goal is to study the impact of preemption (i.e., interrupting the execution of a job and resuming it later by the same or different machine) and failures on the work performance of job processing. We identify features that determine the difficulty of the problem, and in particular, show that the complexity is asymptotically smaller when preemption is allowed.
AB - We study the problem of scheduling n jobs on m identical, fault-prone machines f of which are prone to crashes by an adversary, where communication takes place via a multiple access channel without collision detection. Performance is measured by the total number of available machine steps during the whole execution (work). Our goal is to study the impact of preemption (i.e., interrupting the execution of a job and resuming it later by the same or different machine) and failures on the work performance of job processing. We identify features that determine the difficulty of the problem, and in particular, show that the complexity is asymptotically smaller when preemption is allowed.
UR - http://www.scopus.com/inward/record.url?scp=85070634958&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85070634958&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-25027-0_21
DO - 10.1007/978-3-030-25027-0_21
M3 - Conference contribution
AN - SCOPUS:85070634958
SN - 9783030250263
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 306
EP - 321
BT - Fundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Proceedings
A2 - Gąsieniec, Leszek Antoni
A2 - Jansson, Jesper
A2 - Levcopoulos, Christos
PB - Springer Verlag
T2 - 22nd International Symposium on Fundamentals of Computation Theory, FCT 2019
Y2 - 12 August 2019 through 14 August 2019
ER -