Skip to Main content Skip to Navigation
Journal articles

Fundamental Limits of Decentralized Data Shuffling

Abstract : Data shuffling of training data among different computing nodes (workers) has been identified as a core element to improve the statistical performance of modern large-scale machine learning algorithms. Data shuffling is often considered as one of the most significant bottlenecks in such systems due to the heavy communication load. Under a master-worker architecture (where a master has access to the entire dataset and only communication between the master and the workers is allowed) coding has been recently proved to considerably reduce the communication load. This work considers a different communication paradigm referred to as decentralized data shuffling, where workers are allowed to communicate with one another via a shared link. The decentralized data shuffling problem has two phases: workers communicate with each other during the data shuffling phase, and then workers update their stored content during the storage phase. The main challenge is to derive novel converse bounds and achievable schemes for decentralized data shuffling by considering the asymmetry of the workers' storages (i.e., workers are constrained to store different files in their storages based on the problem setting), in order to characterize the fundamental limits of this problem. For the case of uncoded storage (i.e., each worker directly stores a subset of bits of the dataset), this paper proposes converse and achievable bounds (based on distributed interference alignment and distributed clique-covering strategies) that are within a factor of 3/2 of one another. The proposed schemes are also exactly optimal under the constraint of uncoded storage for either large storage size or at most four workers in the system.
Document type :
Journal articles
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download
Contributor : Delphine Le Piolet <>
Submitted on : Monday, September 28, 2020 - 6:28:26 PM
Last modification on : Wednesday, October 14, 2020 - 4:16:38 AM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2020-12-28

Please log in to resquest access to the document



Kai Wan, Daniela Tuninetti, Mingyue Ji, Giuseppe Caire, Pablo Piantanida. Fundamental Limits of Decentralized Data Shuffling. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2020, 66 (6), pp.3616-3637. ⟨10.1109/tit.2020.2966197⟩. ⟨hal-02951653⟩



Record views