Coded computing has proved its efficiency in handling a straggler issue in distributed computing framework. It uses error correcting codes to mitigate the effect of the stragglers. However, in a coded distributed computing framework, there may exist Byzantine workers who send the wrong computation results to a master in order to contaminate the overall computation output. Therefore, it is essential to identify Byzantine workers from their computation results in coded computing. In this paper, we consider Byzantine attack identification problem in coded computing for distributed matrix multiplication tasks. We propose a new coding scheme which facilitates the efficient Byzantine attack identification, namely locally testable codes. We also suggest a hierarchical group testing method for Byzantine attack identification. We claim the required number of tests for group testing in our scheme, and show that it requires smaller number of tests than the conventional group testing method for the existing coded computing schemes.
In a distributed computing environment, there may exist slow processing workers, which are known as “stragglers”, and they can slow down the whole computing process. In this article, we consider coded computation for matrix multiplication tasks in distributed computing, which can mitigate the effect of stragglers by a coding approach. We propose a new communication-efficient coded computation scheme, namely squeezed polynomial codes, for a straggler-exploiting scenario where multiple sub-tasks are assigned to the workers to partially leverage the computation capability of stragglers. The key idea of squeezed polynomial codes is to overlap the encoded matrices in assigning multiple sub-tasks with appropriate polynomial functions in order to reduce the task-allocation communication load from a master to its workers. We compare squeezed polynomial codes with the existing schemes for distributed matrix multiplication in a communication load perspective. Consequently, we show that squeezed polynomial codes can efficiently reduce the communication load while ensuring the optimal recovery condition at a master to obtain final product.
Distributed computing has emerged as a promising solution for accelerating machine learning training processes on large-scale datasets by leveraging the parallel processing capabilities of multiple workers. However, there remain two major issues that still need to be addressed: i) Byzantine attacks from malicious workers, and ii) the effect of slow workers, commonly referred to as stragglers. In this paper, we address both issues concurrently by introducing Group-wise Verifiable Coded Computing (GVCC), a novel approach that combines coding techniques and group-wise verification to enhance robustness against Byzantine attacks and resilience to straggler effects in distributed computing. The key idea of GVCC is to verify a group of computation results from workers at a time, while providing resilience to stragglers through encoding tasks assigned to workers with Group-wise Verifiable Codes. We evaluate the performance of GVCC through experiments conducted on Amazon EC2 clouds and the results show that GVCC outperforms the existing methods in terms of overall processing time and verification time while maintaining the verification performance. This study highlights the potential of GVCC as an effective solution for overcoming the challenges of Byzantine attacks and stragglers in distributed computing for executing matrix multiplication.
12 January 2023 in IEEE Transactions on Communications
In this paper, we consider coded computation for matrix multiplication tasks in distributed computing to mitigate straggler effects. We assume that the stragglers’ computation results can be leveraged at the master by assigning multiple sub-tasks to the workers. We propose a new coded computation scheme, namely Chebyshev coded fully private matrix multiplication (CFP), to preserve the privacy of a master in a scenario where a master wants to obtain a matrix multiplication result from the libraries which are shared by the workers, while concealing both of the two indices of the desired matrices from each worker. The key idea of CFP is to introduce Chebyshev polynomials, which have commutative property, in queries sent to workers to allocate sub-tasks. We also extend CFP to keep the privacy of a master from colluding workers. In conclusion, we show that CFP can preserve the privacy of a master from each worker and efficiently mitigate straggler effects compared to existing schemes.
Mixup is a powerful data augmentation strategy that has been shown to improve the generalization and adversarial robustness of machine learning classifiers, particularly in computer vision applications. Despite its simplicity and effectiveness, the impact of Mixup on the fairness of a model has not been thoroughly investigated yet. In this paper, we demonstrate that Mixup can perpetuate or even exacerbate bias presented in the training set. We provide insight to understand the reasons behind this behavior and propose GBMix, a group-balanced Mixup strategy to train fair classifiers. It groups the dataset based on their attributes and balances the Mixup ratio between the groups. Through the reorganization and balance of Mixup among groups, GBMix effectively enhances both average and worst-case accuracy concurrently. We empirically show that GBMix effectively mitigates bias in the training set and reduces the performance gap between groups. This effect is observed across a range of datasets and networks, and GBMix outperforms all the state-of-the-art methods.