Search

Federated learning (FL) is a popular technique for training a global model on data distributed across client devices. Like other distributed training techniques, FL is susceptible to straggler (slower or failed) clients. Recent work has proposed to address this through device-to-device (D2D) offloading, which introduces privacy concerns. In this paper, we propose a novel straggler-optimal approach for coded matrix computations which can significantly reduce the communication delay and privacy issues introduced from D2D data transmissions in FL. Moreover, our proposed approach leads to a considerable improvement of the local computation speed when the generated data matrix is sparse. Numerical evaluations confirm the superiority of our proposed method over baseline approaches., Comment: arXiv admin note: text overlap with arXiv:2301.12685

We consider a quantum and classical version multi-party function computation problem with $n$ players, where players $2, \dots, n$ need to communicate appropriate information to player 1, so that a ``generalized'' inner product function with an appropriate promise can be calculated. The communication complexity of a protocol is the total number of bits that need to be communicated. When $n$ is prime and for our chosen function, we exhibit a quantum protocol (with complexity $(n-1) \log n$ bits) and a classical protocol (with complexity $(n-1)^2 (\log n^2$) bits). In the quantum protocol, the players have access to entangled qudits but the communication is still classical. Furthermore, we present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.

Polynomial based approaches, such as the Mat-Dot and entangled polynomial codes (EPC) have been used extensively within coded matrix computations to obtain schemes with good recovery thresholds. However, these schemes are well-recognized to suffer from poor numerical stability in decoding. Moreover, the encoding process in these schemes involves linearly combining a large number of input submatrices, i.e., the encoding weight is high. For the practically relevant case of sparse input matrices, this can have the undesirable effect of significantly increasing the worker node computation time. In this work, we propose a generalization of the EPC scheme by combining the idea of gradient coding along with the basic EPC encoding. Our technique allows us to reduce the weight of the encoding and arrive at schemes that exhibit much better numerical stability; this is achieved at the expense of a worse threshold. By appropriately setting parameters in our scheme, we recover several well-known schemes in the literature. Simulation results show that our scheme provides excellent numerical stability and fast computation speed (for sparse input matrices) as compared to EPC and Mat-Dot codes., 8 pages, 3 figures, 2 tables. Minor typos corrected

Straggler nodes are well-known bottlenecks of distributed matrix computations which induce reductions in computation/communication speeds. A common strategy for mitigating such stragglers is to incorporate Reed-Solomon based MDS (maximum distance separable) codes into the framework; this can achieve resilience against an optimal number of stragglers. However, these codes assign dense linear combinations of submatrices to the worker nodes. When the input matrices are sparse, these approaches increase the number of non-zero entries in the encoded matrices, which in turn adversely affects the worker computation time. In this work, we develop a distributed matrix computation approach where the assigned encoded submatrices are random linear combinations of a small number of submatrices. In addition to being well suited for sparse input matrices, our approach continues have the optimal straggler resilience in a certain range of problem parameters. Moreover, compared to recent sparse matrix computation approaches, the search for a ``good'' set of random coefficients to promote numerical stability in our method is much more computationally efficient. We show that our approach can efficiently utilize partial computations done by slower worker nodes in a heterogeneous system which can enhance the overall computation speed. Numerical experiments conducted through Amazon Web Services (AWS) demonstrate up to 30% reduction in per worker node computation time and 100x faster encoding compared to the available methods.

A plethora of modern machine learning tasks require the utilization of large-scale distributed clusters as a critical component of the training pipeline. However, abnormal Byzantine behavior of the worker nodes can derail the training and compromise the quality of the inference. Such behavior can be attributed to unintentional system malfunctions or orchestrated attacks; as a result, some nodes may return arbitrary results to the parameter server (PS) that coordinates the training. Recent work considers a wide range of attack models and has explored robust aggregation and/or computational redundancy to correct the distorted gradients. In this work, we consider attack models ranging from strong ones: $q$ omniscient adversaries with full knowledge of the defense protocol that can change from iteration to iteration to weak ones: $q$ randomly chosen adversaries with limited collusion abilities which only change every few iterations at a time. Our algorithms rely on redundant task assignments coupled with detection of adversarial behavior. We also show the convergence of our method to the optimal point under common assumptions and settings considered in literature. For strong attacks, we demonstrate a reduction in the fraction of distorted gradients ranging from 16%-99% as compared to the prior state-of-the-art. Our top-1 classification accuracy results on the CIFAR-10 data set demonstrate 25% advantage in accuracy (averaged over strong and weak scenarios) under the most sophisticated attacks compared to state-of-the-art methods., 21 pages, 17 figures, 6 tables. The material in this work appeared in part at arXiv:2108.02416 which has been published at the 2022 IEEE International Symposium on Information Theory

The current BigData era routinely requires the processing of large scale data on massive distributed computing clusters. Such large scale clusters often suffer from the problem of "stragglers", which are defined as slow or failed nodes. The overall speed of a computational job on these clusters is typically dominated by stragglers in the absence of a sophisticated assignment of tasks to the worker nodes. In recent years, approaches based on coding theory (referred to as "coded computation") have been effectively used for straggler mitigation. Coded computation offers significant benefits for specific classes of problems such as distributed matrix computations (which play a crucial role in several parts of the machine learning pipeline). The essential idea is to create redundant tasks so that the desired result can be recovered as long as a certain number of worker nodes complete their tasks. In this survey article, we overview recent developments in the field of coding for straggler-resilient distributed matrix computations., To appear in the Special Issue on Distributed, Streaming Machine Learning in the IEEE Signal Processing Magazine, 2020

Training of large scale models on distributed clusters is a critical component of the machine learning pipeline. However, this training can easily be made to fail if some workers behave in an adversarial (Byzantine) fashion whereby they return arbitrary results to the parameter server (PS). A plethora of existing papers consider a variety of attack models and propose robust aggregation and/or computational redundancy to alleviate the effects of these attacks. In this work we consider an omniscient attack model where the adversary has full knowledge about the gradient computation assignments of the workers and can choose to attack (up to) any q out of K worker nodes to induce maximal damage. Our redundancy-based method ByzShield leverages the properties of bipartite expander graphs for the assignment of tasks to workers; this helps to effectively mitigate the effect of the Byzantine behavior. Specifically, we demonstrate an upper bound on the worst case fraction of corrupted gradients based on the eigenvalues of our constructions which are based on mutually orthogonal Latin squares and Ramanujan graphs. Our numerical experiments indicate over a 36% reduction on average in the fraction of corrupted gradients compared to the state of the art. Likewise, our experiments on training followed by image classification on the CIFAR-10 dataset show that ByzShield has on average a 20% advantage in accuracy under the most sophisticated attacks. ByzShield also tolerates a much larger fraction of adversarial nodes compared to prior work., Comment: 17 pages, 12 figures

In distributed computing systems, it is well recognized that worker nodes that are slow (called stragglers) tend to dominate the overall job execution time. Coded computation utilizes concepts from erasure coding to mitigate the effect of stragglers by running "coded" copies of tasks comprising a job. Stragglers are typically treated as erasures in this process. While this is useful, there are issues with applying, e.g., MDS codes in a straightforward manner. Specifically, several applications such as matrix-vector products deal with sparse matrices. MDS codes typically require dense linear combinations of submatrices of the original matrix which destroy their inherent sparsity. This is problematic as it results in significantly higher processing times for computing the submatrix-vector products in coded computation. Furthermore, it also ignores partial computations at stragglers. In this work, we propose a fine-grained model that quantifies the level of non-trivial coding needed to obtain the benefits of coding in matrix-vector computation. Simultaneously, it allows us to leverage partial computations performed by the straggler nodes. For this model, we propose and evaluate several code designs and discuss their properties., Comment: 5 pages, 3 figures, to appear at the 2018 IEEE Information Theory Workshop (ITW), in Guangzhou, China

In this work we present a flexible, probabilistic and reference-free method of error correction for high throughput DNA sequencing data. The key is to exploit the high coverage of sequencing data and model short sequence outputs as independent realizations of a Hidden Markov Model (HMM). We pose the problem of error correction of reads as one of maximum likelihood sequence detection over this HMM. While time and memory considerations rule out an implementation of the optimal Baum-Welch algorithm (for parameter estimation) and the optimal Viterbi algorithm (for error correction), we propose low-complexity approximate versions of both. Specifically, we propose an approximate Viterbi and a sequential decoding based algorithm for the error correction. Our results show that when compared with Reptile, a state-of-the-art error correction method, our methods consistently achieve superior performances on both simulated and real data sets., Comment: Submitted to ISIT 2013

We consider the design and analysis of the efficiently-encodable rate-compatible ($E^2RC$) irregular LDPC codes proposed in previous work. In this work we introduce semi-structured $E^2RC$-like codes and protograph $E^2RC$ codes. EXIT chart based methods are developed for the design of semi-structured $E^2RC$-like codes that allow us to determine near-optimal degree distributions for the systematic part of the code while taking into account the structure of the deterministic parity part, thus resolving one of the open issues in the original construction. We develop a fast EXIT function computation method that does not rely on Monte-Carlo simulations and can be used in other scenarios as well. Our approach allows us to jointly optimize code performance across the range of rates under puncturing. We then consider protograph $E^2RC$ codes (that have a protograph representation) and propose rules for designing a family of rate-compatible punctured protographs with low thresholds. For both the semi-structured and protograph $E^2RC$ families we obtain codes whose gap to capacity is at most 0.3 dB across the range of rates when the maximum variable node degree is twenty., To appear in IEEE Journal on Selected Areas in Communications, special issue on Capacity Approaching Codes, 2009

The deterministic channel model for wireless relay networks proposed by Avestimehr, Diggavi and Tse `07 has captured the broadcast and inference nature of wireless communications and has been widely used in approximating the capacity of wireless relay networks. The authors generalized the max-flow min-cut theorem to the linear deterministic wireless relay networks and characterized the unicast capacity of such deterministic network as the minimum rank of all the binary adjacency matrices describing source-destination cuts whose number grows exponentially with the size of the network. In this paper, we developed a fast algorithm for finding the unicast capacity of a linear deterministic wireless relay network by finding the maximum number of linearly independent paths using the idea of path augmentation. We developed a modified depth-first search algorithm tailored for the linear deterministic relay networks for finding linearly independent paths whose total number proved to equal the unicast capacity of the underlying network. The result of our algorithm suggests a capacity-achieving transmission strategy with one-bit length linear encoding at the relay nodes in the concerned linear deterministic wireless relay network. The correctness of our algorithm for universal cases is given by our proof in the paper. Moreover, our algorithm has a computational complexity bounded by $O(|{\cal{V}}_x|\cdot C^4+d\cdot |{\cal{V}}_x|\cdot C^3)$ which shows a significant improvement over the previous results for solving the same problem by Amaudruz and Fragouli (whose complexity is bounded by $O(M\cdot |{\cal{E}}|\cdot C^5)$ with $M\geq d$ and $|{\cal{E}}|\geq|{\cal{V}}_x|$) and by Yazdi and Savari (whose complexity is bounded by $O(L^8\cdot M^{12}\cdot h_0^3+L\cdot M^6\cdot C\cdot h_0^4)$ with $h_0\geq C$)., Comment: 27 pages

We consider a communication network with a single source that has a set of messages and two terminals where each terminal is interested in an arbitrary subset of messages at the source. A tight capacity region for this problem is demonstrated. We show by a simple graph-theoretic procedure that any such problem can be solved by performing network coding on the subset of messages that are requested by both the terminals and that routing is sufficient for transferring the remaining messages., Comment: 4 pages, appeared at the Canadian Workshop on Information Theory (CWIT), 2005

We present a new class of irregular low-density parity-check (LDPC) codes for moderate block lengths (up to a few thousand bits) that are well-suited for rate-compatible puncturing. The proposed codes show good performance under puncturing over a wide range of rates and are suitable for usage in incremental redundancy hybrid-automatic repeat request (ARQ) systems. In addition, these codes are linear-time encodable with simple shift-register circuits. For a block length of 1200 bits the codes outperform optimized irregular LDPC codes and extended irregular repeat-accumulate (eIRA) codes for all puncturing rates 0.6~0.9 (base code performance is almost the same) and are particularly good at high puncturing rates where good puncturing performance has been previously difficult to achieve., Accepted subject to minor revision to IEEE Trans. on Comm