Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes.

We consider the setting of a Master server, M, who possesses confidentialdata (e.g., personal, genomic or medical data) and wants to run intensivecomputations on it, as part of a machine learning algorithm for example. TheMaster wants to distribute these computations to untrusted workers who havevolunteered or are incentivized to help with this task. However, the data mustbe kept private and not revealed to the individual workers. Some of the workersmay be stragglers, e.g., slow or busy, and will take a random time to finishthe task assigned to them. We are interested in reducing the delays experiencedby the Master. We focus on linear computations as an essential operation inmany iterative algorithms such as principal component analysis, support vectormachines and other gradient-descent based algorithms. A classical solution isto use a linear secret sharing scheme, such as Shamir's scheme, to divide thedata into secret shares on which the workers can perform linear computations.However, classical codes can provide straggler mitigation assuming a worst-casescenario of a fixed number of stragglers. We propose a solution based on newsecure codes, called Staircase codes, introduced previously by two of theauthors. Staircase codes allow flexibility in the number of stragglers up to agiven maximum, and universally achieve the information theoretic limit on thedownload cost by the Master, leading to latency reduction. Under the shiftedexponential model, we find upper and lower bounds on the Master's mean waitingtime. We derive the distribution of the Master's waiting time, and its mean,for systems with up to two stragglers. For systems with any number ofstragglers, we derive an expression that can give the exact distribution, andthe mean, of the waiting time of the Master. We show that Staircase codesalways outperform classical secret sharing codes.