Performing Partially Ordered Sets of Jobs on a MAC in Presence of Adversarial Crashes

Klonowski, Marek, Kowalski, Dariusz R, Mirek, Jaroslaw and Wong, Prudence WH ORCID: 0000-0001-7935-7245 (2019) Performing Partially Ordered Sets of Jobs on a MAC in Presence of Adversarial Crashes. In: 2019 IEEE 18th International Symposium on Network Computing and Applications (NCA), 2019-9-26 - 2019-9-28.

Text
nca2019.pdf - Author Accepted Manuscript
Download (194kB) | Preview

Official URL: http://dx.doi.org/10.1109/nca.2019.8935017

Abstract

We study the problem of scheduling n similar jobs on m machines, with respect to the fact that jobs are dependent and some of them must be performed before others. Dependencies between jobs are modeled as a partial order relation. Machines are prone to crashes, induced by an Adaptive f-Bounded adversary who can fail up to f machines, where 0 ≤ f < m. Communication takes place via a Multiple-Access Channel (MAC), which restricts simultaneous transmissions. We show an optimal solution (with respect to total work of all machines) for partially ordered sets of jobs forming chains and an algorithm and lower bound for trees.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	19 Sep 2019 16:00
Last Modified:	15 Mar 2024 07:20
DOI:	10.1109/nca.2019.8935017
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3055220