Fault-Tolerant Parallel Scheduling of Arbitrary Length Jobs on a Shared Channel

Marek Klonowski, Dariusz R. Kowalski, Jarosław Mirek, Prudence W.H. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationFundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Proceedings
EditorsLeszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos
PublisherSpringer Verlag
Pages306-321
Number of pages16
ISBN (Print)9783030250263
DOIs
StatePublished - 2019
Event22nd International Symposium on Fundamentals of Computation Theory, FCT 2019 - Copenhagen, Denmark
Duration: Aug 12 2019Aug 14 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11651 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Symposium on Fundamentals of Computation Theory, FCT 2019
Country/TerritoryDenmark
CityCopenhagen
Period8/12/198/14/19

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Fault-Tolerant Parallel Scheduling of Arbitrary Length Jobs on a Shared Channel'. Together they form a unique fingerprint.

Cite this