Secure Distributed Computing With Straggling Servers Using Polynomial Codes

By Heecheol Yang, Jungwoo Lee. 2019

115 citations recorded by the source corpus.

In this paper, we consider a secure distributed computing scenario in which a master wants to perform matrix multiplication of confidential inputs with multiple workers in parallel. In such a setting, a master does not want to reveal information about the two input matrices to the workers in an information-theoretic sense. We propose a secure distributed computing scheme that can efficiently cope with straggling effects by applying polynomial codes on sub-tasks assigned to workers. The achievable recovery threshold, i.e., the number of workers that a master needs to wait for to get the final product, of our proposed scheme is revealed to be order-optimal to the number of workers. Moreover, we derive the achievable recovery threshold of the proposed scheme is within a constant multiplicative factor from information-theoretic lower bound. As a byproduct, we extend our strategy to secure distributed computing for convolution tasks on confidential data.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

On the Upload versus Download Cost for Secure and Private Matrix Multiplication (2019, background): “Later, [6], [7] studied the problem of secure distributed matrix multiplication.”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, background): “Among topics for future work, we mention here the establishment of matching converse bounds [16] and the”
Private Secure Coded Computation (2019, methodology): “For the data security, the master jointly encode A and a random matrix R into polynomial codes where the random matrix R is exclusively owned by the master and concealed to the workers, which was previously proposed in [5].”
GASP Codes for Secure Distributed Matrix Multiplication (2018, methodology): “This was done since the previous literature on this subject, [1], [2], and [5], all used the download rate as their measure of performance.”