TY - JOUR
T1 - Adaptive Private Distributed Matrix Multiplication
AU - Bitar, Rawad
AU - Xhemrishi, Marvin
AU - Wachter-Zeh, Antonia
N1 - Publisher Copyright:
© 1963-2012 IEEE.
PY - 2022/4/1
Y1 - 2022/4/1
N2 - We consider the problem of designing codes with flexible rate (referred to as rateless codes), for private distributed matrix-matrix multiplication. A master server owns two private matrices A and B and hires worker nodes to help computing their multiplication. The matrices should remain information-theoretically private from the workers. Codes with fixed rate require the master to assign tasks to the workers and then wait for a predetermined number of workers to finish their assigned tasks. The size of the tasks, hence the rate of the scheme, depends on the number of workers that the master waits for. We design a rateless private matrix-matrix multiplication scheme, called RPM3. In contrast to fixed-rate schemes, our scheme fixes the size of the tasks and allows the master to send multiple tasks to the workers. The master keeps sending tasks and receiving results until it can decode the multiplication; rendering the scheme flexible and adaptive to heterogeneous environments. Despite resulting in a smaller rate than known straggler-tolerant schemes, RPM3 provides a smaller mean waiting time of the master by leveraging the heterogeneity of the workers. The waiting time is studied under two different models for the workers' service time. We provide upper and lower bounds for the mean waiting time under both models. In addition, we provide lower bounds on the mean waiting time under the worker-dependent fixed service time model.
AB - We consider the problem of designing codes with flexible rate (referred to as rateless codes), for private distributed matrix-matrix multiplication. A master server owns two private matrices A and B and hires worker nodes to help computing their multiplication. The matrices should remain information-theoretically private from the workers. Codes with fixed rate require the master to assign tasks to the workers and then wait for a predetermined number of workers to finish their assigned tasks. The size of the tasks, hence the rate of the scheme, depends on the number of workers that the master waits for. We design a rateless private matrix-matrix multiplication scheme, called RPM3. In contrast to fixed-rate schemes, our scheme fixes the size of the tasks and allows the master to send multiple tasks to the workers. The master keeps sending tasks and receiving results until it can decode the multiplication; rendering the scheme flexible and adaptive to heterogeneous environments. Despite resulting in a smaller rate than known straggler-tolerant schemes, RPM3 provides a smaller mean waiting time of the master by leveraging the heterogeneity of the workers. The waiting time is studied under two different models for the workers' service time. We provide upper and lower bounds for the mean waiting time under both models. In addition, we provide lower bounds on the mean waiting time under the worker-dependent fixed service time model.
KW - Private rateless codes
KW - double-sided private matrix multiplication
KW - information-theoretic privacy
KW - partial stragglers
UR - http://www.scopus.com/inward/record.url?scp=85123307343&partnerID=8YFLogxK
U2 - 10.1109/TIT.2022.3143199
DO - 10.1109/TIT.2022.3143199
M3 - Article
AN - SCOPUS:85123307343
SN - 0018-9448
VL - 68
SP - 2653
EP - 2673
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 4
ER -