Fundamental Limits of Decentralized Data Shuffling - CentraleSupélec Accéder directement au contenu
Article Dans Une Revue IEEE Transactions on Information Theory Année : 2020

Fundamental Limits of Decentralized Data Shuffling

Résumé

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.
Fichier principal
Vignette du fichier
fundamental_limits_piantanida_arxiv.pdf (782.13 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02951653 , version 1 (28-09-2020)
hal-02951653 , version 2 (21-09-2021)
hal-02951653 , version 3 (19-01-2022)
hal-02951653 , version 4 (22-06-2023)

Identifiants

Citer

Kai Wan, Daniela Tuninetti, Mingyue Ji, Giuseppe Caire, Pablo Piantanida. Fundamental Limits of Decentralized Data Shuffling. IEEE Transactions on Information Theory, 2020, 66 (6), pp.3616-3637. ⟨10.1109/tit.2020.2966197⟩. ⟨hal-02951653v1⟩
103 Consultations
139 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More