Coded distributed computing adapts to changing worker clusters efficiently
Coded Computing for Dynamic System via a Cartesian Product
Information Theory
Summary
When groups of computers work together to handle big tasks, sometimes some computers leave and new ones join. The authors studied how to keep things running smoothly without redoing all the work already assigned. They created a new method that mixes old and new storage plans to handle general computing jobs even when the worker setup changes. Their system can reassign unfinished tasks and use all available computers for messaging, making the overall process efficient.
What this means in practice
- •For cloud infrastructure teams: Optimize task distribution when server clusters join or leave without redeploying all data storage from scratch.
- •For data center network schedulers: Improve communication efficiency by enabling even idle workers to participate in coded multicasting under changing cluster membership.
Authors
Chenglin Li, Minquan Cheng, Youlong Wu
Abstract
This paper studies coded distributed computing (CDC) in a dynamic system in which workers may depart and new clusters may join. The caches of the surviving workers and their existing Reduce assignments stay untouched, while the storage brought by arriving clusters is put to use. In contrast to elastic computing, which targets linear functions, and to dynamic coded caching, which requires placement across all users, the model considered here accommodates general MapReduce tasks under a placement that is partly fixed and partly new. The proposed scheme builds cluster-wise placement delivery arrays (PDAs) and couples them through a Cartesian product. A delivery-aware rule reassigns the abandoned Reduce functions, and a generalized communication PDA allows even workers that hold no Reduce function to serve as coded transmitters. For arbitrary feasible disconnections, the exact load is derived. A file-wise converse for instantly decodable XOR multicasts shows that, in the absence of disconnections, the scheme lies within a factor of two of the best scheme in this multicast class when new clusters arrive, and within a factor of four otherwise, even when the benchmark optimizes over all feasible uncoded placements.