Share Email Print

Proceedings Paper

Codes for straggler mitigation in secure distributed linear regression
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

We consider the setting of a master server who possesses confidential data (genomic, medical data, etc.) and wants to run linear regression on this data, as part of a machine learning algorithm for example. The master wants to distribute these computations to untrusted workers who have volunteered or are incentivized to help with this task. However, the data must be kept private (in an information theoretic sense) and not revealed to the individual workers. The workers may be busy and will take a random time to finish the task assigned to them. We are interested in reducing the aggregate delay experienced by the master. A known solution is to use a linear secret sharing scheme to divide the data into secret shares on which the workers can compute. However, classical codes can provide straggler mitigation assuming a worst-case scenario of a fixed number of stragglers. We introduce a new family of codes called Staircase codes that allow flexibility in the number of stragglers up to a given maximum, and universally achieve the information theoretic limit on the download cost by the Master, leading to latency reduction. Under the shifted exponential model, we find upper and lower bounds on the Master's mean waiting time. We derive the distribution of the Master's waiting time, and its mean, for systems with up to two stragglers. We show that Staircase codes always outperform classical secret sharing codes. For instance, Staircase codes can lead to up to $59%$ reduction in delay compared to classical secret sharing codes. We validate our results with extensive implementation on Amazon EC2 clusters.

Paper Details

Date Published: 10 May 2019
PDF: 1 pages
Proc. SPIE 11013, Disruptive Technologies in Information Sciences II, 110130Z (10 May 2019); doi: 10.1117/12.2533349
Show Author Affiliations
Rawad Bitar, Rutgers, The State Univ. of New Jersey (United States)
Salim El Rouayheb, Rutgers Univ. (United States)

Published in SPIE Proceedings Vol. 11013:
Disruptive Technologies in Information Sciences II
Misty Blowers; Russell D. Hall; Venkateswara R. Dasari, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?