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
In large-scale distributed computing, a "master" node delegates tasks to multiple "workers." Two major hurdles often arise in these systems: stragglers and privacy. Stragglers are workers that are inevitably slower than others due to network congestion or hardware issues, creating a bottleneck for the entire process. "Coded computation" solves this by using erasure codes so the master only needs a subset of workers to finish the task.
Privacy is equally critical. In many applications, such as an AI assistant processing user data, the master might need to compute a function using a specific dataset from a library shared among workers. However, the master may want to keep which dataset it is using a secret from those workers. Existing solutions for Private Information Retrieval (PIR) can be slow and do not always integrate well with techniques used to mitigate stragglers. This paper bridges that gap by introducing Private Coded Computation.
Methodology
The authors propose Private Polynomial Codes for matrix multiplication. The core idea is to represent the master's data and the worker's library as polynomials.
Encoding and Privacy
The master encodes its own data ($A$) and sends it to workers. It then sends queries that instruct workers how to encode the entire library ($B$) into a single "private" polynomial. This encoding is designed so that the desired dataset ($B_D$) is mathematically masked among the other datasets in the library. Privacy is "information-theoretic," meaning even a worker with infinite computing power could not determine which dataset the master requested based on the queries received. This is formally defined by the privacy constraint $I(D; Q_i^D, C_i^D, R_i^D, B) = 0$, ensuring zero mutual information between the desired index $D$ and the information available to the worker.
Implementation Strategies
- Private One-Shot Polynomial Codes: Each worker is assigned one large sub-task. This approach is simple and has low communication overhead but remains somewhat vulnerable to the "slowest of the fastest" workers.
- Private Asynchronous Polynomial Codes: The master breaks the task into many small sub-tasks. Workers process these sequentially and return partial results. Faster workers complete more tasks, while slow workers (stragglers) still contribute what they can. This asynchronous flow ensures that no worker sits idle, minimizing overall runtime.
Experimental Evaluation
The paper evaluates these schemes using simulated environments for matrix multiplication ($A \times B_D$).
- System Parameters: Simulations typically used $N=12$ workers and a library of $M=4$ categories.
- Modeling Latency: Worker computation times were modeled using an exponential distribution, the standard academic benchmark for simulating real-world cloud computing jitter and straggler effects.
Results and Discussion
The private asynchronous scheme achieved a 20% to 60% reduction in computation time compared to both the one-shot version and conventional Robust PIR (RPIR) schemes. As the variability in worker speeds (the "straggling parameter") increased, the advantage of the asynchronous approach became more pronounced.
Unlike traditional coded computation, which ignores the slowest workers entirely, the asynchronous method exploits faster workers more efficiently by letting them "run ahead" and complete more work. However, there is a fundamental trade-off: the asynchronous method is much faster but requires the master to send more evaluation points (higher bandwidth) compared to the one-shot method.
Conclusion
While Private Polynomial Codes offer significant speedups and privacy, they come with increased communication overhead, particularly in the asynchronous model. Future work could involve applying these private coding principles to more complex structures, such as entangled polynomial codes, to improve efficiency for high-dimensional operations. Additionally, the current privacy proof assumes non-colluding workers; addressing potential collusion remains an open area for research.
Summary updated