Abstract
In a distributed computing system for the master-worker framework, an erasure code can mitigate the effects of slow workers, also called stragglers. The distributed computing system combined with coding is referred to as coded computation. We introduce a variation of coded computation that protects the master's privacy from the workers, which is referred to as private coded computation. In private coded computation, the master needs to compute a function of its own dataset and one of the datasets in a library exclusively shared by the external workers. After the master recovers the result of the desired function through coded computation, the workers should not know which dataset in the library was desired by the master, which implies that the master's privacy is protected. We propose a private coded computation scheme for matrix multiplication, namely private polynomial codes, based on polynomial codes for conventional coded computation. As special cases of private polynomial codes, we propose private one-shot polynomial codes and private asynchronous polynomial codes. Whereas the private one-shot polynomial code achieves a lower communication load from the master to each worker, the private asynchronous polynomial code achieves faster computation than private one-shot polynomial codes. In terms of computation time and communication load, we compare private one-shot polynomial codes and private asynchronous polynomial codes with a conventional robust private information retrieval scheme which can be directly applied to coded computation.
Introduction
Distributed computing systems often rely on a master node delegating massive tasks to multiple worker nodes. However, two primary challenges hinder efficiency and security: the "straggler" problem, where slow workers create bottlenecks, and privacy concerns regarding the master's data interests. For instance, in recommendation systems, a master might request a computation involving a specific category from a shared library without wanting to reveal which category was selected to the external workers.
This paper introduces Private Coded Computation, a framework that bridges the gap between coded computation (using erasure codes to mitigate stragglers) and Private Information Retrieval (PIR). The goal is to perform distributed matrix multiplication while maintaining information-theoretic privacy against non-colluding workers.
System Model and Methods
The proposed framework involves a master node with a private dataset $A$ and a library of datasets $B = \{B_i\}_{i=1}^M$ shared among $N$ workers. The master aims to compute $f(A, B_D)$ for a specific index $D \in [M]$ while keeping $D$ private.
The core of the solution lies in Private Polynomial Codes, which extend standard polynomial codes. The master encodes its private data $A$ and the library $B$ into polynomials. Two specific variations are explored:
- Private One-Shot Polynomial Codes: The master sends a single evaluation of the encoded data to each worker. This minimizes communication overhead but does not fully exploit the varying speeds of workers.
- Private Asynchronous Polynomial Codes: The master partitions the data into smaller sub-tasks. Faster workers can complete multiple sub-results, while slower workers contribute what they can, effectively reducing idle time and mitigating the straggler effect.
Privacy is achieved through a "symmetry" mechanism. By evaluating the "undesired" parts of the library at random points and the "desired" part at a specific point, the master ensures that the queries sent to workers are mathematically indistinguishable regardless of the chosen index $D$, ensuring information-theoretic privacy.
Performance Evaluation
The framework was evaluated using synthetic matrix multiplication over finite fields ($F_q$) and simulated worker latency modeled by an exponential distribution, a standard benchmark in distributed computing research.
Key results include:
- Computation Speed: Private asynchronous polynomial codes achieved a 60% reduction in computation time compared to the one-shot version in a 12-worker simulation.
- Benchmark Comparison: The proposed schemes outperformed conventional Robust Private Information Retrieval (RPIR) benchmarks by approximately 20% in total runtime.
- Recovery Threshold: Successful recovery of the matrix product is guaranteed once the master receives at least $K = mn$ sub-computation results, where $m$ and $n$ are partitioning parameters.
Conclusion and Future Work
While the proposed schemes offer significant improvements in speed and privacy, they rely on the assumption that workers do not collude. Additionally, the asynchronous mode's higher communication load may be a drawback in bandwidth-constrained environments. Future research will explore entangled polynomial codes to further optimize recovery thresholds and communication efficiency for more complex distributed tasks.
Summary updated