Timely Distributed Computation With Stragglers

Baturalp Buyukates; Sennur Ulukus

doi:10.1109/TCOMM.2020.3001873

Timely Distributed Computation With Stragglers

Baturalp Buyukates
, Sennur Ulukus

Research output: Contribution to journal › Article › peer-review

Abstract

We consider a status update system in which the update packets need to be processed to extract the embedded useful information. The source node sends the acquired information to a computation unit (CU) which consists of a master node and n worker nodes. The master node distributes the received computation task to the worker nodes. Upon computation, the master node aggregates the results and sends them back to the source node to keep it updated. We investigate the age performance of uncoded and coded (repetition coded, MDS coded, and multi-message MDS (MM-MDS) coded) schemes in the presence of stragglers under i.i.d. exponential transmission delays and i.i.d shifted exponential computation times. We show that asymptotically MM-MDS coded scheme outperforms the other schemes. Furthermore, we characterize the optimal codes such that the average age is minimized.

Original language	English
Article number	9115646
Pages (from-to)	5273-5282
Number of pages	10
Journal	IEEE Transactions on Communications
Volume	68
Issue number	9
DOIs	https://doi.org/10.1109/TCOMM.2020.3001873
Publication status	Published - 1 Sept 2020
Externally published	Yes

Keywords

Delays
Task analysis
Computational modeling
Information age
Random variables
Data mining

Access to Document

10.1109/TCOMM.2020.3001873

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9115646

Cite this

@article{6cdab8dd94654bf3b8c41787a1434d5f,

title = "Timely Distributed Computation With Stragglers",

abstract = "We consider a status update system in which the update packets need to be processed to extract the embedded useful information. The source node sends the acquired information to a computation unit (CU) which consists of a master node and n worker nodes. The master node distributes the received computation task to the worker nodes. Upon computation, the master node aggregates the results and sends them back to the source node to keep it updated. We investigate the age performance of uncoded and coded (repetition coded, MDS coded, and multi-message MDS (MM-MDS) coded) schemes in the presence of stragglers under i.i.d. exponential transmission delays and i.i.d shifted exponential computation times. We show that asymptotically MM-MDS coded scheme outperforms the other schemes. Furthermore, we characterize the optimal codes such that the average age is minimized.",

keywords = "Delays, Task analysis, Computational modeling, Information age, Random variables, Data mining",

author = "Baturalp Buyukates and Sennur Ulukus",

year = "2020",

month = sep,

day = "1",

doi = "10.1109/TCOMM.2020.3001873",

language = "English",

volume = "68",

pages = "5273--5282",

journal = "IEEE Transactions on Communications",

issn = "1558-0857",

publisher = "IEEE",

number = "9",

}

TY - JOUR

T1 - Timely Distributed Computation With Stragglers

AU - Buyukates, Baturalp

AU - Ulukus, Sennur

PY - 2020/9/1

Y1 - 2020/9/1

N2 - We consider a status update system in which the update packets need to be processed to extract the embedded useful information. The source node sends the acquired information to a computation unit (CU) which consists of a master node and n worker nodes. The master node distributes the received computation task to the worker nodes. Upon computation, the master node aggregates the results and sends them back to the source node to keep it updated. We investigate the age performance of uncoded and coded (repetition coded, MDS coded, and multi-message MDS (MM-MDS) coded) schemes in the presence of stragglers under i.i.d. exponential transmission delays and i.i.d shifted exponential computation times. We show that asymptotically MM-MDS coded scheme outperforms the other schemes. Furthermore, we characterize the optimal codes such that the average age is minimized.

AB - We consider a status update system in which the update packets need to be processed to extract the embedded useful information. The source node sends the acquired information to a computation unit (CU) which consists of a master node and n worker nodes. The master node distributes the received computation task to the worker nodes. Upon computation, the master node aggregates the results and sends them back to the source node to keep it updated. We investigate the age performance of uncoded and coded (repetition coded, MDS coded, and multi-message MDS (MM-MDS) coded) schemes in the presence of stragglers under i.i.d. exponential transmission delays and i.i.d shifted exponential computation times. We show that asymptotically MM-MDS coded scheme outperforms the other schemes. Furthermore, we characterize the optimal codes such that the average age is minimized.

KW - Delays

KW - Task analysis

KW - Computational modeling

KW - Information age

KW - Random variables

KW - Data mining

UR - https://ieeexplore.ieee.org/document/9115646/

U2 - 10.1109/TCOMM.2020.3001873

DO - 10.1109/TCOMM.2020.3001873

M3 - Article

SN - 1558-0857

VL - 68

SP - 5273

EP - 5282

JO - IEEE Transactions on Communications

JF - IEEE Transactions on Communications

IS - 9

M1 - 9115646

ER -

Timely Distributed Computation With Stragglers

Abstract

Keywords

Access to Document

Fingerprint

Cite this