Lune

INFOCOM2020Top-tier venue

Sequential addition of coded sub-tasks for straggler mitigation

Ajay Badita, Parimal Parag, Vaneet Aggarwal

Abstract

Straggler mitigation can be achieved by redundant computation. In MDS redundancy method, a task is divided into k sub-tasks which are encoded to n coded sub-tasks, such that a task is completed if any k coded sub-tasks are completed. Two important metrics of interest are task completion time, and server utilization cost which is the aggregate completed work by all servers in this duration. We consider a proactive straggler mitigation strategy where n0 out of n coded sub-tasks are started at time 0 while the remaining n-n0 coded sub-tasks are launched when ℓ0 min(n0, k) of the initial ones finish. The coded subtasks are halted when k of them finish. For this flexible forking strategy with multiple parameters, we analyze the mean of two performance metrics for the proposed forking strategy when the random service completion time at each server is independent and distributed identically to a shifted exponential. Our analysis demonstrates that the regime of n0 < k leads to higher mean service completion time and no change in mean server utilization cost as compared to no forking (n0 = n), and is thus not a regime of interest. For n0 k, we find that there is a tradeoff between the two performance metrics and leads to decrease in mean server utilization cost at the expense of mean service completion time and an efficient choice of the parameters is helpful.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Incentive Mechanism Design for Distributed Coded Machine LearningNingning Ding, Zhixuan Fang, Lingjie Duan, Jianwei HuangINFOCOM 2021 · 20 citations
  2. Leveraging partial stragglers within gradient codingAditya Ramamoorthy, Ruoyu Meng, Vrinda S. GirimajiNeurIPS 2024 · 7 citations
  3. Equitable Scheduling on a Single MachineKlaus Heeger, Danny Hermelin, George B. Mertzios, Hendrik Molter et al.AAAI 2021 · 20 citations
  4. Stream Iterative Distributed Coded Computing for Learning Applications in Heterogeneous SystemsHoma Esfahanizadeh, Alejandro Cohen, Muriel MédardINFOCOM 2022 · 9 citations
  5. Coded Sequential Matrix Multiplication For Straggler MitigationM. Nikhil Krishnan, Seyederfan Hosseini, Ashish KhistiNeurIPS 2020 · 8 citations
Dusk over the sea between two cliffs drawn in fine vertical lines