Diversity vs. parallelism in distributed computing with redundancy

Pei Peng, Emina Soljanin, Philip Whiting

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

Distributed computing enables parallel execution of tasks that make up a large computing job. Random fluctuations in service times (inherent to computing environments) often cause a non-negligible number of straggling tasks with long completion time. Redundancy, in the form of task replication and erasure coding, has emerged as a potentially powerful way to curtail the variability in service time, as it provides diversity that allows a job to be completed when only a subset of redundant tasks gets executed. Thus both redundancy and parallelism reduce the execution time, but compete for resources of the system. In situations of constrained resources (here fixed number of parallel servers), increasing redundancy reduces the available level of parallelism. We characterize the diversity vs. parallelism tradeoff for three common models of task size dependent execution times. We find that different models operate optimally at different levels of redundancy, and thus may require very different code rates.

Original languageEnglish
Title of host publication2020 IEEE International Symposium on Information Theory
Subtitle of host publicationproceedings
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages257-262
Number of pages6
ISBN (Electronic)9781728164328, 9781728164311
ISBN (Print)9781728164335
DOIs
Publication statusPublished - 2020
Event2020 IEEE International Symposium on Information Theory, ISIT 2020 - Virtual, Los Angeles, United States
Duration: 21 Jul 202026 Jul 2020

Publication series

Name
ISSN (Print)2157-8095
ISSN (Electronic)2157-8117

Conference

Conference2020 IEEE International Symposium on Information Theory, ISIT 2020
CountryUnited States
CityLos Angeles
Period21/07/2026/07/20

Fingerprint

Dive into the research topics of 'Diversity vs. parallelism in distributed computing with redundancy'. Together they form a unique fingerprint.

Cite this