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

Marek Klonowski, Dariusz R. Kowalski, Jaroslaw Mirek, Prudence W. H. WongFCT 2019 · DOI

Abstract

This paper addresses the challenge of scheduling $n$ jobs of arbitrary lengths on $m$ processors that are subject to crashes and communicate via a shared Multiple Access Channel (MAC) without collision detection. We explore the fundamental trade-offs between preemption, randomization, and adversarial models. Our analysis reveals a significant "preemption gap" and demonstrates that while randomization can circumvent deterministic lower bounds against non-adaptive adversaries, it offers no asymptotic advantage against adaptive ones. We present three algorithms—ScaTri, DefTri, and RanScaTri—and provide tight work complexity bounds for each.

Introduction

In distributed computing, scheduling tasks efficiently in the presence of faults is a core problem. While much literature focuses on unit-length tasks, real-world applications often involve jobs of varying durations. This paper investigates the "Task-Performing" problem in a particularly constrained environment: machines share a single communication channel where simultaneous broadcasts result in noise (no collision detection), and an adversary can crash a subset of machines.

The primary metric of interest is work complexity, defined as the total number of steps taken by all machines (including idle time and failed attempts) until all $n$ jobs are completed and reported.

System Model and Challenges

We consider a system of $m$ identical processors and $n$ jobs with a total length $L = \sum \ell_i$, where $\ell_i$ is the length of job $i$ and $\alpha = \max \ell_i$. The communication model is a Multiple Access Channel (MAC) where:

  1. If exactly one machine broadcasts, the message is successful.
  2. If zero or more than one machine broadcasts, the channel is silent (no collision detection).

The adversary can crash up to $f < m$ machines. We distinguish between:

  • Preemptive vs. Non-preemptive: Whether a job can be interrupted and resumed later by another machine.
  • Adaptive vs. Non-adaptive Adversary: Whether the adversary can observe the algorithm's execution (including random choices) before deciding which machines to crash.

Proposed Algorithms

ScaTri (Scaling-Triangle)

ScaTri is designed for the preemptive setting. It employs a "triangle" strategy, organizing tasks into epochs of increasing sizes. To handle the uncertainty of machine availability, the algorithm "rescales" the triangle: if the number of remaining tasks is small, it reduces epoch sizes to minimize idle time and communication overhead.

DefTri (Deforming-Triangle)

In the non-preemptive setting, work lost due to a crash cannot be recovered. DefTri addresses this by "deforming" the communication schedule. It adjusts the intervals between broadcast attempts based on the average length of remaining jobs, ensuring that machines attempt to report progress only after a job is likely completed.

RanScaTri

RanScaTri introduces randomization to the ScaTri framework. It uses a "Mix-And-Test" procedure where machines randomly decide whether to act as "leaders" for reporting. This randomization is specifically aimed at defeating non-adaptive adversaries who cannot react to the specific random choices made during execution.

Key Results and Complexity Analysis

The paper's main contribution is a comprehensive mapping of work complexity across different constraints. A central finding is the Preemption Gap: non-preemptive scheduling is fundamentally more expensive because a crash near the end of a long job results in the total loss of that effort.

Furthermore, the study clarifies the role of randomization. Against a non-adaptive adversary, randomization allows for an expected work complexity that matches the deterministic preemptive bound even in some more restricted settings. However, against an adaptive adversary, the benefits of randomization vanish asymptotically.

Summary of work complexity bounds across different scheduling paradigms.

As shown in the figure above, the authors establish tight bounds for most scenarios. For instance, in the preemptive setting, the ScaTri algorithm achieves a work complexity of $L + \mathcal{O}(m\sqrt{L} + m \min\{f, L\} + m\alpha)$, which is asymptotically optimal.

Conclusion

This work provides a rigorous theoretical foundation for scheduling arbitrary length jobs in fault-prone shared-channel environments. The results highlight that preemption is a powerful tool for efficiency and that the power of randomization is strictly limited by the adversary's ability to observe the system. Future research may explore the impact of collision detection or models where jobs arrive dynamically over time.

Summary updated

BibTeX
@inproceedings{klonowski2019fault,
  author = {Marek Klonowski and Dariusz R. Kowalski and Jaroslaw Mirek and Prudence W. H. Wong},
  title = {{Fault-Tolerant Parallel Scheduling of Arbitrary Length Jobs on a Shared Channel}},
  booktitle = {FCT},
  year = {2019},
  doi = {10.1007/978-3-030-25027-0\_21},
}
Figure