Adaptive Private Distributed Matrix Multiplication

Rawad Bitar, Marvin Xhemrishi, Antonia Wachter-Zeh

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)2653-2673
Number of pages21
JournalIEEE Transactions on Information Theory
Volume68
Issue number4
DOIs
StatePublished - 1 Apr 2022

Keywords

  • Private rateless codes
  • double-sided private matrix multiplication
  • information-theoretic privacy
  • partial stragglers

Fingerprint

Dive into the research topics of 'Adaptive Private Distributed Matrix Multiplication'. Together they form a unique fingerprint.

Cite this