Preserving Sparsity and Privacy in Straggler-Resilient Distributed Matrix Computations
Date
2023-08-08
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
arXiv
Abstract
Existing approaches to distributed matrix computations involve allocating coded combinations of submatrices to worker nodes, to build resilience to stragglers and/or enhance privacy. In this study, we consider the challenge of preserving input sparsity in such approaches to retain the associated computational efficiency enhancements. First, we find a lower bound on the weight of coding, i.e., the number of submatrices to be combined to obtain coded submatrices to provide the resilience to the maximum possible number of stragglers (for given number of nodes and their storage constraints). Next we propose a distributed matrix computation scheme which meets this exact lower bound on the weight of the coding. Further, we develop controllable trade-off between worker computation time and the privacy constraint for sparse input matrices in settings where the worker nodes are honest but curious. Numerical experiments conducted in Amazon Web Services (AWS) validate our assertions regarding straggler mitigation and computation speed for sparse matrices.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
Preprint
Comments
This is a preprint from Das, Anindya Bijoy, Aditya Ramamoorthy, David J. Love, and Christopher G. Brinton. "Preserving Sparsity and Privacy in Straggler-Resilient Distributed Matrix Computations." arXiv preprint arXiv:2308.04331 (2023). doi: https://doi.org/10.48550/arXiv.2308.04331. Copyright 2023 The Authors. CC By