Delay-optimal policies in partial fork-join systems with redundancy and random slowdowns

Martin Zubeldia (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We consider a large distributed service system consisting of $n$ homogeneous servers with infinite capacity FIFO queues. Jobs arrive as a Poisson process of rate $\lambda n/k_n$ (for some positive constant $\lambda$ and integer $k_n$). Each incoming job consists of $k_n$ identical tasks that can be executed in parallel, and that can be encoded into at least $k_n$ "replicas" of the same size (by introducing redundancy) so that the job is considered to be completed when any $k_n$ replicas associated with it finish their service. Moreover, we assume that servers can experience random slowdowns in their processing rate so that the service time of a replica is the product of its size and a random slowdown. First, we assume that the server slowdowns are shifted exponential and independent of the replica sizes. In this setting we show that the delay of a typical job is asymptotically minimized (as $n\to\infty$) when the number of replicas per task is a constant that only depends on the arrival rate $\lambda$, and on the expected slowdown of servers. Second, we introduce a new model for the server slowdowns in which larger tasks experience less variable slowdowns than smaller tasks. In this setting we show that, under the class of policies where all replicas start their service at the same time, the delay of a typical job is asymptotically minimized (as $n\to\infty$) when the number of replicas per task is made to depend on the actual size of the tasks being replicated, with smaller tasks being replicated more than larger tasks.
Original languageEnglish
Article number2
Number of pages49
JournalProceedings of the ACM on Measurement and Analysis of Computing Systems
Volume4
Issue number1
DOIs
Publication statusPublished - 1 May 2020

Bibliographical note

69 pages

Fingerprint Dive into the research topics of 'Delay-optimal policies in partial fork-join systems with redundancy and random slowdowns'. Together they form a unique fingerprint.

Cite this