Fault-tolerant parallel scheduling of different length jobs on a multiple-access channel Article Swipe
YOU?
·
· 2017
· Open Access
·
We study the problem of scheduling jobs on fault-prone machines communicating via a shared channel, also known as multiple-access channel. We have $n$ arbitrary length jobs to be scheduled on $m$ identical machines, $f$ of which are prone to crashes by an adversary. A machine can inform other machines when a job is completed via the channel without collision detection. Performance is measured by the total number of available machine steps during the whole execution. Our goal is to study the impact of preemption (i.e., interrupting the execution of a job and resuming later in the same or different machine) and failures on the work performance of job processing. The novelty is the ability to identify the features that determine the complexity (difficulty) of the problem. We show that the problem becomes difficult when preemption is not allowed, by showing corresponding lower and upper bounds, the latter with algorithms reaching them. We also prove that randomization helps even more, but only against a non-adaptive adversary; in the presence of more severe adaptive adversary, randomization does not help in any setting. Our work has extended from previous work that focused on settings including: scheduling on multiple-access channel without machine failures, complete information about failures, or incomplete information about failures (like in this work) but with unit length jobs and, hence, without considering preemption.
Related Topics
- Type
- article
- Language
- en
- Landing Page
- https://arxiv.org/abs/1710.07380v1
- OA Status
- green
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W2768130550
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2768130550Canonical identifier for this work in OpenAlex
- Title
-
Fault-tolerant parallel scheduling of different length jobs on a multiple-access channelWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2017Year of publication
- Publication date
-
2017-10-20Full publication date if available
- Authors
-
Marek Klonowski, Dariusz R. Kowalski, Jarosław Mirek, Prudence W. H. WongList of authors in order
- Landing page
-
https://arxiv.org/abs/1710.07380v1Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/abs/1710.07380v1Direct OA link when available
- Concepts
-
Computer science, Preemption, Scheduling (production processes), Adversary, Novelty, Fault tolerance, Channel (broadcasting), Distributed computing, Computer network, Computer security, Mathematical optimization, Mathematics, Operating system, Philosophy, TheologyTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2768130550 |
|---|---|
| doi | |
| ids.mag | 2768130550 |
| ids.openalex | https://openalex.org/W2768130550 |
| fwci | 0.0 |
| type | article |
| title | Fault-tolerant parallel scheduling of different length jobs on a multiple-access channel |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12288 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9991999864578247 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1705 |
| topics[0].subfield.display_name | Computer Networks and Communications |
| topics[0].display_name | Optimization and Search Problems |
| topics[1].id | https://openalex.org/T10551 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.9933000206947327 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2209 |
| topics[1].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[1].display_name | Scheduling and Optimization Algorithms |
| topics[2].id | https://openalex.org/T10772 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9925000071525574 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Distributed systems and fault tolerance |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.7702783346176147 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C206952183 |
| concepts[1].level | 2 |
| concepts[1].score | 0.70320063829422 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q1193100 |
| concepts[1].display_name | Preemption |
| concepts[2].id | https://openalex.org/C206729178 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5951026678085327 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q2271896 |
| concepts[2].display_name | Scheduling (production processes) |
| concepts[3].id | https://openalex.org/C41065033 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5210475325584412 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2825412 |
| concepts[3].display_name | Adversary |
| concepts[4].id | https://openalex.org/C2778738651 |
| concepts[4].level | 2 |
| concepts[4].score | 0.46363967657089233 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q16546687 |
| concepts[4].display_name | Novelty |
| concepts[5].id | https://openalex.org/C63540848 |
| concepts[5].level | 2 |
| concepts[5].score | 0.46220728754997253 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q3140932 |
| concepts[5].display_name | Fault tolerance |
| concepts[6].id | https://openalex.org/C127162648 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4481469988822937 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q16858953 |
| concepts[6].display_name | Channel (broadcasting) |
| concepts[7].id | https://openalex.org/C120314980 |
| concepts[7].level | 1 |
| concepts[7].score | 0.42007631063461304 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q180634 |
| concepts[7].display_name | Distributed computing |
| concepts[8].id | https://openalex.org/C31258907 |
| concepts[8].level | 1 |
| concepts[8].score | 0.26943352818489075 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q1301371 |
| concepts[8].display_name | Computer network |
| concepts[9].id | https://openalex.org/C38652104 |
| concepts[9].level | 1 |
| concepts[9].score | 0.206377774477005 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q3510521 |
| concepts[9].display_name | Computer security |
| concepts[10].id | https://openalex.org/C126255220 |
| concepts[10].level | 1 |
| concepts[10].score | 0.16162779927253723 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[10].display_name | Mathematical optimization |
| concepts[11].id | https://openalex.org/C33923547 |
| concepts[11].level | 0 |
| concepts[11].score | 0.1077856719493866 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[11].display_name | Mathematics |
| concepts[12].id | https://openalex.org/C111919701 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q9135 |
| concepts[12].display_name | Operating system |
| concepts[13].id | https://openalex.org/C138885662 |
| concepts[13].level | 0 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q5891 |
| concepts[13].display_name | Philosophy |
| concepts[14].id | https://openalex.org/C27206212 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q34178 |
| concepts[14].display_name | Theology |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.7702783346176147 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/preemption |
| keywords[1].score | 0.70320063829422 |
| keywords[1].display_name | Preemption |
| keywords[2].id | https://openalex.org/keywords/scheduling |
| keywords[2].score | 0.5951026678085327 |
| keywords[2].display_name | Scheduling (production processes) |
| keywords[3].id | https://openalex.org/keywords/adversary |
| keywords[3].score | 0.5210475325584412 |
| keywords[3].display_name | Adversary |
| keywords[4].id | https://openalex.org/keywords/novelty |
| keywords[4].score | 0.46363967657089233 |
| keywords[4].display_name | Novelty |
| keywords[5].id | https://openalex.org/keywords/fault-tolerance |
| keywords[5].score | 0.46220728754997253 |
| keywords[5].display_name | Fault tolerance |
| keywords[6].id | https://openalex.org/keywords/channel |
| keywords[6].score | 0.4481469988822937 |
| keywords[6].display_name | Channel (broadcasting) |
| keywords[7].id | https://openalex.org/keywords/distributed-computing |
| keywords[7].score | 0.42007631063461304 |
| keywords[7].display_name | Distributed computing |
| keywords[8].id | https://openalex.org/keywords/computer-network |
| keywords[8].score | 0.26943352818489075 |
| keywords[8].display_name | Computer network |
| keywords[9].id | https://openalex.org/keywords/computer-security |
| keywords[9].score | 0.206377774477005 |
| keywords[9].display_name | Computer security |
| keywords[10].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[10].score | 0.16162779927253723 |
| keywords[10].display_name | Mathematical optimization |
| keywords[11].id | https://openalex.org/keywords/mathematics |
| keywords[11].score | 0.1077856719493866 |
| keywords[11].display_name | Mathematics |
| language | en |
| locations[0].id | mag:2768130550 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | arXiv (Cornell University) |
| locations[0].landing_page_url | https://arxiv.org/abs/1710.07380v1 |
| authorships[0].author.id | https://openalex.org/A5069460529 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-3141-8712 |
| authorships[0].author.display_name | Marek Klonowski |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Marek Klonowski |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5101948468 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-1316-7788 |
| authorships[1].author.display_name | Dariusz R. Kowalski |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Dariusz R. Kowalski |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5004328745 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-1254-975X |
| authorships[2].author.display_name | Jarosław Mirek |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Jarosław Mirek |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5063692696 |
| authorships[3].author.orcid | https://orcid.org/0000-0001-7935-7245 |
| authorships[3].author.display_name | Prudence W. H. Wong |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Prudence W. H. Wong |
| authorships[3].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/abs/1710.07380v1 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Fault-tolerant parallel scheduling of different length jobs on a multiple-access channel |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-10-10T17:16:08.811792 |
| primary_topic.id | https://openalex.org/T12288 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9991999864578247 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1705 |
| primary_topic.subfield.display_name | Computer Networks and Communications |
| primary_topic.display_name | Optimization and Search Problems |
| related_works | https://openalex.org/W2765296791, https://openalex.org/W2210788865, https://openalex.org/W2967081197, https://openalex.org/W1553768272, https://openalex.org/W2044575758, https://openalex.org/W1603821301, https://openalex.org/W1987917925, https://openalex.org/W838614691, https://openalex.org/W3101628343, https://openalex.org/W2887280043, https://openalex.org/W3153341931, https://openalex.org/W85828273, https://openalex.org/W1979055695, https://openalex.org/W2022455167, https://openalex.org/W290186175, https://openalex.org/W287729638, https://openalex.org/W315980484, https://openalex.org/W2121393783, https://openalex.org/W87349826, https://openalex.org/W268568750 |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | mag:2768130550 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | arXiv (Cornell University) |
| best_oa_location.landing_page_url | https://arxiv.org/abs/1710.07380v1 |
| primary_location.id | mag:2768130550 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | arXiv (Cornell University) |
| primary_location.landing_page_url | https://arxiv.org/abs/1710.07380v1 |
| publication_date | 2017-10-20 |
| publication_year | 2017 |
| referenced_works_count | 0 |
| abstract_inverted_index.A | 43 |
| abstract_inverted_index.a | 12, 50, 89, 162 |
| abstract_inverted_index.We | 0, 20, 126, 151 |
| abstract_inverted_index.an | 41 |
| abstract_inverted_index.as | 17 |
| abstract_inverted_index.be | 27 |
| abstract_inverted_index.by | 40, 63, 138 |
| abstract_inverted_index.in | 94, 165, 177, 209 |
| abstract_inverted_index.is | 52, 61, 77, 111, 135 |
| abstract_inverted_index.of | 4, 34, 67, 82, 88, 106, 123, 168 |
| abstract_inverted_index.on | 7, 29, 102, 189, 193 |
| abstract_inverted_index.or | 97, 203 |
| abstract_inverted_index.to | 26, 38, 78, 114 |
| abstract_inverted_index.$f$ | 33 |
| abstract_inverted_index.$m$ | 30 |
| abstract_inverted_index.$n$ | 22 |
| abstract_inverted_index.Our | 75, 180 |
| abstract_inverted_index.The | 109 |
| abstract_inverted_index.and | 91, 100, 142 |
| abstract_inverted_index.any | 178 |
| abstract_inverted_index.are | 36 |
| abstract_inverted_index.but | 159, 212 |
| abstract_inverted_index.can | 45 |
| abstract_inverted_index.has | 182 |
| abstract_inverted_index.job | 51, 90, 107 |
| abstract_inverted_index.not | 136, 175 |
| abstract_inverted_index.the | 2, 55, 64, 72, 80, 86, 95, 103, 112, 116, 120, 124, 129, 145, 166 |
| abstract_inverted_index.via | 11, 54 |
| abstract_inverted_index.also | 15, 152 |
| abstract_inverted_index.and, | 217 |
| abstract_inverted_index.does | 174 |
| abstract_inverted_index.even | 157 |
| abstract_inverted_index.from | 184 |
| abstract_inverted_index.goal | 76 |
| abstract_inverted_index.have | 21 |
| abstract_inverted_index.help | 176 |
| abstract_inverted_index.jobs | 6, 25, 216 |
| abstract_inverted_index.more | 169 |
| abstract_inverted_index.only | 160 |
| abstract_inverted_index.same | 96 |
| abstract_inverted_index.show | 127 |
| abstract_inverted_index.that | 118, 128, 154, 187 |
| abstract_inverted_index.this | 210 |
| abstract_inverted_index.unit | 214 |
| abstract_inverted_index.when | 49, 133 |
| abstract_inverted_index.with | 147, 213 |
| abstract_inverted_index.work | 104, 181, 186 |
| abstract_inverted_index.(like | 208 |
| abstract_inverted_index.about | 201, 206 |
| abstract_inverted_index.helps | 156 |
| abstract_inverted_index.known | 16 |
| abstract_inverted_index.later | 93 |
| abstract_inverted_index.lower | 141 |
| abstract_inverted_index.more, | 158 |
| abstract_inverted_index.other | 47 |
| abstract_inverted_index.prone | 37 |
| abstract_inverted_index.prove | 153 |
| abstract_inverted_index.steps | 70 |
| abstract_inverted_index.study | 1, 79 |
| abstract_inverted_index.them. | 150 |
| abstract_inverted_index.total | 65 |
| abstract_inverted_index.upper | 143 |
| abstract_inverted_index.which | 35 |
| abstract_inverted_index.whole | 73 |
| abstract_inverted_index.work) | 211 |
| abstract_inverted_index.(i.e., | 84 |
| abstract_inverted_index.during | 71 |
| abstract_inverted_index.hence, | 218 |
| abstract_inverted_index.impact | 81 |
| abstract_inverted_index.inform | 46 |
| abstract_inverted_index.latter | 146 |
| abstract_inverted_index.length | 24, 215 |
| abstract_inverted_index.number | 66 |
| abstract_inverted_index.severe | 170 |
| abstract_inverted_index.shared | 13 |
| abstract_inverted_index.ability | 113 |
| abstract_inverted_index.against | 161 |
| abstract_inverted_index.becomes | 131 |
| abstract_inverted_index.bounds, | 144 |
| abstract_inverted_index.channel | 56, 195 |
| abstract_inverted_index.crashes | 39 |
| abstract_inverted_index.focused | 188 |
| abstract_inverted_index.machine | 44, 69, 197 |
| abstract_inverted_index.novelty | 110 |
| abstract_inverted_index.problem | 3, 130 |
| abstract_inverted_index.showing | 139 |
| abstract_inverted_index.without | 57, 196, 219 |
| abstract_inverted_index.adaptive | 171 |
| abstract_inverted_index.allowed, | 137 |
| abstract_inverted_index.channel, | 14 |
| abstract_inverted_index.channel. | 19 |
| abstract_inverted_index.complete | 199 |
| abstract_inverted_index.extended | 183 |
| abstract_inverted_index.failures | 101, 207 |
| abstract_inverted_index.features | 117 |
| abstract_inverted_index.identify | 115 |
| abstract_inverted_index.machine) | 99 |
| abstract_inverted_index.machines | 9, 48 |
| abstract_inverted_index.measured | 62 |
| abstract_inverted_index.presence | 167 |
| abstract_inverted_index.previous | 185 |
| abstract_inverted_index.problem. | 125 |
| abstract_inverted_index.reaching | 149 |
| abstract_inverted_index.resuming | 92 |
| abstract_inverted_index.setting. | 179 |
| abstract_inverted_index.settings | 190 |
| abstract_inverted_index.arbitrary | 23 |
| abstract_inverted_index.available | 68 |
| abstract_inverted_index.collision | 58 |
| abstract_inverted_index.completed | 53 |
| abstract_inverted_index.determine | 119 |
| abstract_inverted_index.different | 98 |
| abstract_inverted_index.difficult | 132 |
| abstract_inverted_index.execution | 87 |
| abstract_inverted_index.failures, | 198, 202 |
| abstract_inverted_index.identical | 31 |
| abstract_inverted_index.machines, | 32 |
| abstract_inverted_index.scheduled | 28 |
| abstract_inverted_index.adversary, | 172 |
| abstract_inverted_index.adversary. | 42 |
| abstract_inverted_index.adversary; | 164 |
| abstract_inverted_index.algorithms | 148 |
| abstract_inverted_index.complexity | 121 |
| abstract_inverted_index.detection. | 59 |
| abstract_inverted_index.execution. | 74 |
| abstract_inverted_index.including: | 191 |
| abstract_inverted_index.incomplete | 204 |
| abstract_inverted_index.preemption | 83, 134 |
| abstract_inverted_index.scheduling | 5, 192 |
| abstract_inverted_index.Performance | 60 |
| abstract_inverted_index.considering | 220 |
| abstract_inverted_index.fault-prone | 8 |
| abstract_inverted_index.information | 200, 205 |
| abstract_inverted_index.performance | 105 |
| abstract_inverted_index.preemption. | 221 |
| abstract_inverted_index.processing. | 108 |
| abstract_inverted_index.(difficulty) | 122 |
| abstract_inverted_index.interrupting | 85 |
| abstract_inverted_index.non-adaptive | 163 |
| abstract_inverted_index.communicating | 10 |
| abstract_inverted_index.corresponding | 140 |
| abstract_inverted_index.randomization | 155, 173 |
| abstract_inverted_index.multiple-access | 18, 194 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/8 |
| sustainable_development_goals[0].score | 0.6399999856948853 |
| sustainable_development_goals[0].display_name | Decent work and economic growth |
| citation_normalized_percentile.value | 0.18901444 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |