检索结果-内蒙古大学图书馆

coded computing and Cooperative Transmission for Wireless Distributed Matrix Multiplication

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第4期69卷 2224-2239页

作者： Li, Kuikui Tao, Meixia Zhang, Jingjing Simeone, Osvaldo Shanghai Jiao Tong Univ Dept Elect Engn Shanghai 200240 Peoples R China Kings Coll London Dept Engn KCLIP Lab London WC2R 2LS England

Consider a multi-cell mobile edge computing network, in which each user wishes to compute the product of a user-generated data matrix with a network-stored matrix. This is done through task offloading by means of input uploading, distributed computing at edge nodes (ENs), and output downloading. Task offloading may suffer long delay since servers at some ENs may be straggling due to random computation time, and wireless channels may experience severe fading and interference. This paper aims to investigate the interplay among upload, computation, and download latencies during the offloading process in the high signal-to-noise ratio regime from an information-theoretic perspective. A policy based on cascaded coded computing and on coordinated and cooperative interference management in uplink and downlink is proposed and proved to be approximately optimal for a sufficiently large upload time. By investing more time in uplink transmission, the policy creates data redundancy at the ENs, which can reduce the computation time, by enabling the use of coded computing, as well as the download time via transmitter cooperation. Moreover, the policy allows computation time to be traded for download time. Numerical examples demonstrate that the proposed policy can improve over existing schemes by significantly reducing the end-to-end execution time.

关键词： Task analysis Servers Downlink Uplink Redundancy Interference Encoding Matrix multiplication straggler edge computing transmission cooperation coded computing

来源：评论

学校读者我要写书评

暂无评论

coded computing for Secure Boolean Computations

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY

引用

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY 2021年第1期2卷 326-337页

作者： Yang, Chien-Sheng Avestimehr, A. Salman Univ Southern Calif Dept Elect & Comp Engn Los Angeles CA 90089 USA

The growing size of modern datasets necessitates splitting a large scale computation into smaller computations and operate in a distributed manner. Adversaries in a distributed system deliberately send erroneous data in order to affect the computation for their benefit. Boolean functions are the key components of many applications, e.g., verification functions in blockchain systems and design of cryptographic algorithms. We consider the problem of computing a Boolean function in a distributed computing system with particular focus on security against Byzantine workers. Any Boolean function can be modeled as a multivariate polynomial with high degree in general. However, the security threshold (i.e., the maximum number of adversarial workers can be tolerated such that the correct results can be obtained) provided by the recent proposed Lagrange coded computing (LCC) can be extremely low if the degree of the polynomial is high. We propose three different schemes called coded Algebraic normal form (ANF), coded Disjunctive normal form (DNF) and coded polynomial threshold function (PTF). The key idea of the proposed schemes is to model it as the concatenation of some low-degree polynomials and threshold functions. In terms of the security threshold, we show that the proposed coded ANF and coded DNF are optimal by providing a matching outer bound.

关键词： Boolean function coded computing distributed computing

来源：评论

学校读者我要写书评

暂无评论

coded computing at Full Speed 40

Coded Computing at Full Speed

引用

40th IEEE International Conference on Distributed computing Systems (ICDCS)

作者： Tang, Bin Cao, Jiannong Cui, Runze Ye, Baoliu Li, Ye Lu, Sanglu Nanjing Univ Natl Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China Hong Kong Polytech Univ Dept Comp Hong Kong Peoples R China Nantong Univ Sch Elect & Informat Nantong Peoples R China

ISBN: (纸本)9781728170022

Distributed computing is the mainstream for large-scale machine learning and big data analytics, but its performance usually suffers from unpredictable stragglers, i.e., very slow nodes. Recently, coded computing has emerged as a new distributed computing paradigm that uses coding-theoretical approaches to mitigate the effect of stragglers. Most existing coding schemes only use the results from a certain number of fastest worker nodes to recover the output and completely ignore the partial work done by other worker nodes, leading to inferior performance. In this paper, for scenarios where each worker node transmits its local result to the master node only after it has finished the whole local computation, we introduce communication at full speed to characterize the full utilization of all the communication links between each worker node that has finished its local computation and the master node, and for scenarios where each worker node computes out the local result piece by piece and can forward each piece once available, we introduce computation at full speed to characterize the full utilization of the work done entirely or partially by all the worker nodes. Considering a general polynomial-based coding framework which encapsulates many advanced coding schemes for a variety of fundamental computing tasks, we propose a randomized approach where each worker node partitions its local result into pieces, generates and forwards random linear combinations of these pieces to the master node sequentially, and theoretically demonstrate that it can lead the coding framework to achieve communication at full speed. For some typical task scenarios, we further show that computation at full speed can be achieved by mapping the encoding operations in the randomized approach into a part of encoding on the input dataset. Experiments conducted on Alibaba Cloud as well as simulations show that our approaches can reduce the total runtime significantly.

关键词： distributed computing coded computing polynomial-based coding straggler tolerance

来源：评论

学校读者我要写书评

暂无评论

Berrut Approximated coded computing: Straggler Resistance Beyond Polynomial computing

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2023年第1期45卷 111-122页

作者： Jahani-Nezhad, Tayyebeh Maddah-Ali, Mohammad Ali Sharif Univ Technol Dept Elect Engn Tehran 111558639 Iran

One of the major challenges in using distributed learning to train complicated models with large data sets is to deal with stragglers effect. As a solution, coded computation has been recently proposed to efficiently add redundancy to the computation tasks. In this technique, coding is used across data sets, and computation is done over coded data, such that the results of an arbitrary subset of worker nodes with a certain size are enough to recover the final results. The major drawbacks with those approaches are (1) they are limited to polynomial functions, (2) the number of servers that we need to wait for grows with the degree of the model, (3) they are not numerically stable for computation over real numbers. In this paper, we propose Berrut Approximated coded computing (BACC), as an alternative approach, as a numerically stable solution, which works beyond polynomial functions computation and with any number of servers. The accuracy of the approximation is established theoretically and verified by simulation. In particular, BACC is used to train a deep neural network on a cluster of servers, which outperforms alternative uncoded solutions in terms of the rate of convergence.

关键词： Distributed learning approximated computing coded computing

来源：评论

学校读者我要写书评

暂无评论

Edge computing in the Dark: Leveraging Contextual-Combinatorial Bandit and coded computing

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2021年第3期29卷 1022-1031页

作者： Yang, Chien-Sheng Pedarsani, Ramtin Avestimehr, A. Salman Univ Southern Calif Dept Elect & Comp Engn Los Angeles CA 90089 USA Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA

With recent advancements in edge computing capabilities, there has been a significant increase in utilizing the edge cloud for event-driven and time-sensitive computations. However, large-scale edge computing networks can suffer substantially from unpredictable and unreliable computing resources which can result in high variability of service quality. We consider the problem of computation offloading over unknown edge cloud networks with a sequence of timely computation jobs. Motivated by the MapReduce computation paradigm, we assume that each computation job can be partitioned to smaller Map functions which are processed at the edge, and the Reduce function is computed at the user after the Map results are collected from the edge nodes. We model the service quality of each edge device as function of context. The user decides the computations to offload to each device with the goal of receiving a recoverable set of computation results in the given deadline. By leveraging the coded computing framework in order to tackle failures or stragglers in computation, we formulate this problem using contextual-combinatorial multi-armed bandits (CC-MAB), and aim to maximize the cumulative expected reward. We propose an online learning policy called online coded edge computing policy, which provably achieves asymptotically-optimal performance in terms of regret loss compared with the optimal offline policy for the proposed CC-MAB problem. In terms of the cumulative reward, it is shown that the online coded edge computing policy significantly outperforms other benchmarks via numerical studies.

关键词： Edge computing Computational modeling Task analysis Processor scheduling Context modeling IEEE transactions Encoding Edge computing coded computing online learning multi-armed bandits

来源：评论

学校读者我要写书评

暂无评论

Group-Wise Verifiable coded computing Under Byzantine Attacks and Stragglers

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2024年 19卷 4344-4357页

作者： Hong, Sangwoo Yang, Heecheol Yoon, Youngseok Lee, Jungwoo Seoul Natl Univ Dept Elect & Comp Engn Commun & Machine Learning Lab Seoul 08826 South Korea Chungnam Natl Univ Div Comp Convergence Distributed Networks & Comp Lab Daejeon 34134 South Korea Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA

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: 1) Byzantine attacks from malicious workers;and 2) 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.

关键词： Task analysis Distributed computing Encoding Codes Resilience Machine learning Decoding Byzantine attacks straggler effect coded computing

来源：评论

学校读者我要写书评

暂无评论

Multiple-Task coded computing for Distributed Computation Framework: Modeling and Delay Analysis

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2024年第8期72卷 5032-5046页

作者： Ji, Zhongming Chen, Li Fu, Hongguang Zhao, Xinghua Xu, Jun Meng, Lingkun Liu, Junwei China Mobile Suzhou Software Technol Co Ltd Suzhou 215000 Peoples R China Univ Sci & Technol China CAS Key Lab Wireless Opt Commun Hefei 230026 Peoples R China

coded computing has received significant attention thanks to its advantage in alleviating the straggler effect in distributed computation framework, which would be one of the key fundamental techniques to enable the distributed and decentralized network architectures towards 5G-advanced and 6G era. Specifically, considering the scenario that multiple tasks randomly arrive at the network, the additional task queuing makes the delay analysis of coded computing more challenging. In this paper, we consider the impacts of task queuing and characterize the end-to-end delay for coded computing systems under the multi-task scenario. To this end, we first model the end-to-end coded computing system. Then, based on the redundant task processing strategies, we consider both purging and non-purging coded computing schemes. Although the expected end-to-end delay for both schemes are intractable, we obtain closed-form expressions for their respective lower and upper bounds, which generalizes the delay results of the single-task scenario. Moreover, we show that the multi-task coded computing has a coding gain of Theta(log n) where n denotes the number of worker nodes, even with task queues considered. Simulation results verify the accuracy of the derived delay bounds and show the effectiveness of coded computing in the multi-task scenario.

关键词： coded computing distributed computation framework delay analysis edge computing queuing theory coded computing distributed computation framework delay analysis edge computing queuing theory

来源：评论

学校读者我要写书评

暂无评论

Delay Optimization of coded computing With Hierarchical Task Partitioning

引用

IEEE COMMUNICATIONS LETTERS 2023年第11期27卷 2899-2903页

作者： Zeng, Qicheng Nan, Zhaojun Zhou, Sheng Tsinghua Univ Beijing Natl Res Ctr Informat Sci & Technol Dept Elect Engn Beijing 100084 Peoples R China

coded computing can combat the straggling effect in distributed computing, especially at the wireless network edge. This letter focuses on the delay optimization of coded computing by jointly considering communication and computation imperfections. We adopt the adaptive privacy-preserving coded computing (APCC) strategy and model the task offloading process as an M/G/1 queueing system. The task division and partitioning problem is formulated as a non-convex mixed-integer non-linear programming (MINLP) with the objective of minimizing the task completion delay. Two near-optimal and low-complexity iterative update algorithms are proposed. Simulation results demonstrate substantial reductions in task completion delay over benchmarks.

关键词： coded computing communication delay hierarchical task partitioning queueing system MINLP

来源：评论

学校读者我要写书评

暂无评论

Numerically Stable Polynomially coded computing

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2021年第5期67卷 2758-2785页

作者： Fahim, Mohammad Cadambe, Viveck R. Penn State Univ Dept Elect Engn University Pk PA 16802 USA Qualcomm Technol Inc San Diego CA 92121 USA

We study the numerical stability of polynomial based encoding methods, which has emerged to be a powerful class of techniques for providing straggler and fault tolerance in the area of coded computing. Our contributions are as follows: 1) We construct new codes for matrix multiplication that achieve the same fault/straggler tolerance as the previously constructed MatDot Codes and Polynomial Codes. 2) We show that the condition number of every m x m sub-matrix of an m x n, n >= m Chebyshev-Vandermonde matrix, evaluated on the n-point Chebyshev grid, grows as O(n(2(n-m))) for n > m. 3) By specializing our orthogonal polynomial based constructions to Chebyshev polynomials, and using our condition number bound for Chebyshev-Vandermonde matrices, we construct new numerically stable techniques for coded matrix multiplication. We empirically demonstrate that our constructions have significantly lower numerical errors compared to previous approaches which involve inversion of Vandermonde matrices. We generalize our constructions to explore the trade-off between computation/communication and fault-tolerance. 4) We propose a numerically stable specialization of Lagrange coded computing. Our approach involves the choice of evaluation points and a suitable decoding procedure. Our approach is demonstrated empirically to have lower numerical errors as compared to standard methods.

关键词： Distributed computing coded computing fault tolerance stragglers numerical stability

来源：评论

学校读者我要写书评

暂无评论

Analog Lagrange coded computing

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY

引用

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY 2021年第1期2卷 283-295页

作者： Soleymani, Mahdi Mahdavifar, Hessam Avestimehr, A. Salman Univ Michigan Ann Arbor Dept Elect Engn & Comp Sci Ann Arbor MI 48104 USA Univ Southern Calif Dept Elect Engn Los Angeles CA 90089 USA

A distributed computing scenario is considered, where the computational power of a set of worker nodes is used to perform a certain computation task over a dataset that is dispersed among the workers. Lagrange coded computing (LCC), proposed by Yu et al., leverages the well-known Lagrange polynomial to perform polynomial evaluation of the dataset in such a scenario in an efficient parallel fashion while keeping the privacy of data amidst possible collusion of workers. This solution relies on quantizing the data into a finite field, so that Shamir's secret sharing, as one of its main building blocks, can be employed. Such a solution, however, is not properly scalable with the size of dataset, mainly due to computation overflows. To address such a critical issue, we propose a novel extension of LCC to the analog domain, referred to as analog LCC (ALCC). All the operations in the proposed ALCC protocol are done over the infinite fields of R/C but for practical implementations floating-point numbers are used. We characterize the privacy of data in ALCC, against any subset of colluding workers up to a certain size, in terms of the distinguishing security (DS) and the mutual information security (MIS) metrics. Also, the accuracy of outcome is characterized in a practical setting assuming operations are performed using floating-point numbers. Consequently, a fundamental trade-off between the accuracy of the outcome of ALCC and its privacy level is observed and is numerically evaluated. Moreover, we implement the proposed scheme to perform matrix-matrix multiplication over a batch of matrices. It is observed that ALCC is superior compared to the state-of-the-art LCC, implemented using fixed-point numbers, assuming both schemes use an equal number of bits to represent data symbols.

关键词： coded computing privacy-preserving computing analog coding

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：