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

coded distributed computing With Predictive Heterogeneous User Demands: A Learning Auction Approach

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2022年第8期40卷 2426-2439页

作者： Zhu, Kun Liang, Jiawei Li, Juan Yi, Changyan Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Peoples R China Collaborat Innovat Ctr Novel Software Technol & I Nanjing 210000 Peoples R China

coded distributed computing(CDC) has shown great potentials to solve the unexpected delay caused by stragglers in distributed computing. In this paper, we focus on the auction design for efficient resource allocation in CDC. Specifically, we aim to design a learning auction mechanism to handle heterogeneous user demands and also to free users from the complexity of specifying valuations for resource combinations, which increases exponentially with the resource dimensions. The user demand type is heterogeneous according to different variation trends of the value with finish time and workload, which is modeled by deep learning. The platform would allocate resources according to the user value function. Then users do not need to consider the complex relationship between uncertain finish time and resource configuration in CDC. Due to the inference error of the learning model and the complexity of calculating uncertain finish time, the considered social welfare optimization problem is a non-linear and non-convex integer problem. Even worse, the typical VCG-based payment scheme cannot guarantee truthfulness with the inference error. In response to these difficulties, we transform the social welfare optimization problem into a mixed integer programming problem which already has efficient solutions. The social welfare gap caused by the inference error is analyzed theoretically. The relationship between the utility regret of reporting truthfully and the inference error is also analyzed. We prove that our mechanism satisfies incentive alignment and individual rationality. Extensive experiments show the superiority of our mechanism compared with existing ones.

关键词： Cost accounting Task analysis Resource management Computational modeling Cloud computing Optimization Encoding coded distributed computing machine learning auction and pricing social welfare maximization MIP optimization

来源：评论

学校读者我要写书评

暂无评论

coded distributed computing Over Unreliable and Insecure D2D Networks

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2024年第5期72卷 2563-2576页

作者： Chen, Jiajun Sung, Chi Wan City Univ Hong Kong Dept Elect Engn Hong Kong Peoples R China

With the development of wireless computing devices, extending distributed computing to wireless networks deserves a closer look. This paper considers distributed computing over unreliable and insecure device-to-device (D2D) networks, in which each device is not always available to perform computation. The process of distributed devices exchanging calculated results with each other is vulnerable to eavesdropping in wireless environments. To handle the unreliable devices, we adopt repetition codes to build a novel system that supports general computations, called rho-replication system, where each device has rho -1 replicas with duplicate data. A coded computation scheme for the $\rho $ -replication system is proposed, which not only achieves the minimum communication load of the system but also ensures weak security of wireless transmissions during data exchange. Furthermore, the replication nature of the system can be exploited for beamforming transmissions, naturally leading to the idea of energy optimization. Simulation results show that increasing rho does not necessarily improve energy efficiency, as the benefit of increased beamforming gain may be outweighed by the drawback of heavier communication load.

关键词： distributed computing Wireless communication Array signal processing Task analysis Security Communication system security Encoding coded distributed computing D2D networks computation replication weak security computation-communication tradeoff energy efficiency

来源：评论

学校读者我要写书评

暂无评论

coded distributed computing for Resilient, Secure and Private Matrix-Vector Multiplication in Edge-Enabled Metaverse

引用

IEEE TRANSACTIONS ON COGNITIVE COMMUNICATIONS AND NETWORKING 2024年第5期10卷 1944-1958页

作者： Qiu, Houming Zhu, Kun Luong, Nguyen Cong Niyato, Dusit Wu, Qiang Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Peoples R China Nanjing Univ Aeronaut & Astronaut Collaborat Innovat Ctr Novel Software Technol & In Nanjing 210016 Peoples R China PHENIKAA Univ Fac Comp Sci Hanoi 12116 Vietnam Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore

Metaverse is an immersive and photorealistic shared virtual world that requires efficient rendering and processing of millions of virtual objects and scenes. This leads to the requirements of computing time-sensitive and computation-intensive tasks, primarily focused on matrix multiplication. Cloud computing can be leveraged to process computation-intensive tasks. However, it is not able to meet the ultra-low latency requirements of immersive experiences due to the remote servers. In this paper, we propose an effectively distributed edge computing framework to compute high-dimensional matrix multiplication for the Metaverse. With the distributed edge computing, the high-dimensional matrix multiplication task is divided into multiple smaller subtasks, which are then assigned to nearby edge servers (workers). However, leveraging distributed edge servers raises emerging issues due to the existence of stragglers, malicious, and colluding servers, which limits the applications of distributed edge computing in the Metaverse system. Thus, we design a resilient, secure, and private coded distributed computing (RSPCDC) scheme to jointly address the aforementioned issues. Firstly, the RSPCDC scheme reduces overall computation latency by lowering the recovery threshold. Secondly, to identify malicious (e.g., Byzantine) workers, a verification approach is embedded in the scheme to promptly detect the Byzantine attack without requiring additional workers. Thirdly, the RSPCDC scheme provides (information-theoretic) privacy protection for the input data against the collusion of workers. Fourthly, the results of subtasks computed by stragglers are fully utilized to enhance the computation performance during the recovery of the final result. In addition, the RSPCDC scheme is designed and deployed in practical scenarios in which the computing resources of the workers are heterogeneous. Extensive performance evaluations are provided to demonstrate the improvement and effectiveness of

关键词： Servers Metaverse Task analysis Codes Edge computing distributed computing Polynomials coded distributed computing edge computing stragglers security privacy matrix-vector recovery threshold

来源：评论

学校读者我要写书评

暂无评论

coded distributed computing for Sparse Functions With Structured Support

Coded Distributed Computing for Sparse Functions With Struct...

引用

IEEE Information Theory Workshop (ITW)

作者： Brunero, Federico Wan, Kai Caire, Giuseppe Elia, Petros EURECOM Sophia Antipolis France Huazhong Univ Sci & Technol Wuhan Peoples R China Tech Univ Berlin Berlin Germany

ISBN: (纸本)9798350301496

coded distributed computing (CDC), originally proposed by Li et al., leverages coded multicast messages to exchange computed intermediate values among the distributed computing nodes, such that the overall communication load could be reduced by a factor of r, the number of input files assigned to each node. However, in the original CDC framework, each output function/task is composed of intermediate values from all input files. In this paper, we propose a new CDC problem for sparse functions with structured support, where each output function depends on a subset of the input files. For a symmetric structured support for which the input files are divided into G equal-length batches and each output function depends on the same number of G' batches, we propose a novel CDC scheme that is strictly better by a factor G/G' than directly employing the original CDC scheme in the considered problem. Furthermore, by proposing a new converse bound, we prove that the communication load of the proposed CDC scheme is order optimal within a constant multiplicative factor of 6.

关键词： Bipartite graph coded distributed computing information-theoretic converse MapReduce structured support

来源：评论

学校读者我要写书评

暂无评论

Asymptotically Optimal coded distributed computing via Combinatorial Designs

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2024年第4期32卷 3018-3033页

作者： Cheng, Minquan Wu, Youlong Li, Xianxian Wu, Dianhua Guangxi Normal Univ Minist Educ Key Lab Educ Blockchain & Intelligent Technol Guilin 541004 Peoples R China Guangxi Normal Univ Guangxi Key Lab Multisource Informat Miningand Sec Guilin 541004 Peoples R China ShanghaiTech Univ Sch Informat Sci & Technol Shanghai 201210 Peoples R China Guangxi Normal Univ Sch Math & Stat Guilin 541006 Peoples R China

coded distributed computing (CDC) introduced by Li et al. can greatly reduce the communication load for MapReduce computing systems. In the cascaded CDC with K workers, N input files and Q output functions, each input file will be mapped by r workers and each output function will be computed by s workers such that coding techniques can be applied to create multicast opportunities. The main drawback of most existing CDC schemes is that they require the original data to be split into a large number of input files that grows exponentially with K , which would significantly increase the coding complexity and degrade the system performance. In this paper, we first use a classical combinatorial structure t -design, for any integer t >= 2 >= 2 , to develop a low-complexity and communication-efficient CDC with r=s. Our scheme has much smaller N and Q than the existing schemes under the same parameters K , r , and s;and achieves smaller communication loads compared with the state-of-the-art schemes when K is relatively large. Remarkably, unlike the previous schemes that realize on large operation fields, our scheme operates in one-shot communication on the minimum binary field F-2 . With a derived lower bound on the communication load under one-shot linear delivery, we show that the t -design scheme is asymptotically optimal. Furthermore, we show that our construction method can incorporate the other combinatorial structures that have a similar property to t -design. For instance, we use t -GDD to obtain another one-shot asymptotically optimal CDC scheme over F-2 that has different parameters from t -design. Finally, we show that our construction method can also be used to construct CDC schemes with r not equal s that have small file number and output function number. Like what you're reading?

关键词： distributed computing Costs Task analysis Encoding Vectors Technological innovation Symbols coded distributed computing asymptotically optimal t-design t-GDD

来源：评论

学校读者我要写书评

暂无评论

Collaborative coded distributed computing Scheme: A Two-Phase Cooperative Game Approach

引用

IEEE ACCESS 2023年 11卷 42042-42051页

作者： Kim, Sungwook Sogang Univ Dept Comp Sci Seoul 04107 South Korea

As a modern communication paradigm, Artificial intelligence based Internet of Things (AIoT) can provide an interactive platform across the globe to enrich the quality of networking services. With the AIoT paradigm, coded distributed computing (CDC) has recently emerged to be a promising solution to address the straggling effects in conventional distributed computing systems. In this article, we propose a novel CDC control scheme in the AIoT platform. Based on the cooperative game theory, the main challenges of our scheme are i) the $k$ value decision for the CDC process, and ii) edge node resource allocation for offloading tasks. Using the ideas of coalition game and weighted Nash social welfare solution (WNSWS), our proposed scheme is developed as a two-phase game model to achieve a mutually desirable solution. At the first phase, a dynamic coalition formation is proceeded to select the most adaptable edge nodes for the offloading subtasks. At the second phase, the WNSWS is adopted to effectively share each edge node's computing resource. Based on the jointly design of these two cooperative games, we explore the synergy effect to optimize the CDC process. In the edge assisted distributed computing infrastructure, our reciprocal combinative approach can provide a fair-efficient solution through the sequential interactions of edge nodes and AIoT devices. In the performance evaluation, we provide extensive simulation analyses to show our scheme's superiority by comparing with the existing baseline protocols.

关键词： Games Internet of Things Artificial intelligence Task analysis Game theory Computational modeling Codes Artificial Internet of Things coded distributed computing dynamic coalition game weighted nash social welfare solution cooperative game theory

来源：评论

学校读者我要写书评

暂无评论

A Family of Binary Locally Repairable Codes for coded distributed computing

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2024年第1期72卷 50-62页

作者： Qharabagh, Muhammad Fetrat Ardakani, Masoud Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada Univ Alberta Dept Elect & Comp Engn Edmonton T6G 2R3 AB Canada

One of the main bottlenecks in distributed computing systems is the stragglers' problem. Error correction codes have been proposed to alleviate this problem at the cost of coding complexity for the master node. In this work, we aim to reduce this coding complexity and propose a novel family of binary locally repairable codes (BLRC) to encode the distributed tasks in a linear matrix-vector multiplication problem. In comparison to the widely used maximum distance separable (MDS) codes, our proposed codes (i) eliminate the costly multiplication operations from the encoding and decoding processes, (ii) allow for low-complexity recovery within the local groups. We analyze the complexity of our proposed codes and through simulations show that compared to MDS codes, our codes reduce the overall encoding plus computation plus decoding time by more than 35% in many practical scenarios.

关键词： Codes Encoding Task analysis Decoding Complexity theory distributed computing Delay effects coded distributed computing stragglers error-correction codes binary codes locally repairable codes minimum distance separable codes computational delay

来源：评论

学校读者我要写书评

暂无评论

New Results on the Computation-Communication Tradeoff for Heterogeneous coded distributed computing

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第4期69卷 2254-2270页

作者： Xu, Fan Shao, Shuo Tao, Meixia Shanghai Jiao Tong Univ Dept Elect Engn Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ Sch Elect Informat & Elect Engn Shanghai 200240 Peoples R China

coded distributed computing (CDC) can alleviate the communication load in distributed computing systems by leveraging coding opportunities via redundant computation. While the optimal computation-communication tradeoff has been well studied for homogeneous systems, it remains largely unknown for heterogeneous systems where workers have different computation capabilities. This paper characterizes the upper and lower bounds of the optimal communication load as two linear programming problems for a general heterogeneous CDC system using the MapReduce framework. Our achievable scheme first designs a parametric data shuffling strategy for any given mapping strategy, and then jointly optimizes the mapping strategy and the data shuffling strategy to obtain the upper bound. The parametric data shuffling strategy allows adjusting the size of the multicast message intended for each worker set, so that it can largely decrease the number of unicast messages and hence increase the communication efficiency. Numerical results show that our achievable communication load is lower than those achieved in existing works. Our lower bound is established by unifying an improved cut-set bound and a peeling method. The obtained upper and lower bounds degenerate to the existing result in homogeneous systems, and coincide with each other when the system is approximately homogeneous or grouped homogeneous.

关键词： distributed computing Multicast communication Linear programming Upper bound Optimization Wireless communication Unicast coded distributed computing heterogeneous system computation-communication tradeoff

来源：评论

学校读者我要写书评

暂无评论

Worker Assignment for Multiple Masters to Speed Up coded distributed computing in Heterogeneous Clusters

引用

IEEE TRANSACTIONS ON SERVICES computing 2023年第3期16卷 2283-2298页

作者： Kim, Daejin Park, Hyegyeong Niyato, Dusit Choi, Junkyun Samsung Elect Suwon South Korea Carnegie Mellon Univ Comp Sci Dept Pittsburgh PA 15213 USA Korea Adv Inst Sci & Technol Sch Electr Engn Daejeon 34141 South Korea Nanyang Technol Univ Sch Comp Sci & Engn SCSE Singapore 639798 Singapore Korea Adv Inst Sci & Technol KAIST Sch Elect Engn Daejeon South Korea

In distributed computing systems, coding has played an important role to robustify the system against the effect of noise, e.g., stragglers, system failures and communication bottlenecks. Most of the existing work has focused on a simple master-worker model with one master and homogeneous workers. However, real-world systems are typically configured with heterogeneous workers distributed to computing nodes and serve multiple tasks in parallel. In this study, we consider the scenario in which multiple masters perform matrix multiplications using the workers having group heterogeneity. The group heterogeneity models that homogeneous workers are located in the same location and regarded as a group;the workers deployed in the different locations are potentially heterogeneous. We propose an asymptotically optimal worker assignment to multiple masters for coded distributed computing in the presence of heterogeneous groups of workers. Specifically, we present a lower bound for the expected latency in terms of the numbers of workers assigned to the masters and the amount of tasks allocated to workers. Adding the concentration constraints on the number of workers allocated to masters, we can obtain the minimum of the lower bound by taking the optimal worker assignment. We find the optimal worker assignment by converting the problem at hand into a linear programming problem. From both numerical simulations and experiments on Amazon EC2 clusters, we confirm that the effect of the proposed worker assignment is significant in various scenarios.

关键词： Task analysis Resource management distributed computing Computational modeling Encoding Load modeling Codes coded distributed computing heterogeneous clusters optimal worker assignment optimal load allocation

来源：评论

学校读者我要写书评

暂无评论

A Comprehensive Survey on coded distributed computing: Fundamentals, Challenges, and Networking Applications

引用

IEEE COMMUNICATIONS SURVEYS AND TUTORIALS 2021年第3期23卷 1800-1837页

作者： Ng, Jer Shyuan Lim, Wei Yang Bryan Luong, Nguyen Cong Xiong, Zehui Asheralieva, Alia Niyato, Dusit Leung, Cyril Miao, Chunyan Nanyang Technol Univ Alibaba Grp & Alibaba NTU Joint Res Inst Singapore Singapore PHENIKAA Univ Fac Comp Sci Hanoi 12116 Vietnam PHENIKAA Univ PHENIKAA Res & Technol Inst Hanoi 12116 Vietnam Singapore Univ Technol Design Pillar Informat Syst Technol & Design Singapore Singapore Southern Univ Sci & Technol Dept Comp Sci & Engn Shenzhen 518055 Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Singapore Singapore Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada Univ British Columbia Joint NTU UBC Res Ctr Excellence Act Living Elder Vancouver BC V6T 1Z4 Canada

distributed computing has become a common approach for large-scale computation tasks due to benefits such as high reliability, scalability, computation speed, and cost-effectiveness. However, distributed computing faces critical issues related to communication load and straggler effects. In particular, computing nodes need to exchange intermediate results with each other in order to calculate the final result, and this significantly increases communication overheads. Furthermore, a distributed computing network may include straggling nodes that run intermittently slower. This results in a longer overall time needed to execute the computation tasks, thereby limiting the performance of distributed computing. To address these issues, coded distributed computing (CDC), i.e., a combination of coding theoretic techniques and distributed computing, has been recently proposed as a promising solution. Coding theoretic techniques have proved effective in WiFi and cellular systems to deal with channel noise. Therefore, CDC may significantly reduce communication load, alleviate the effects of stragglers, provide fault-tolerance, privacy and security. In this survey, we first introduce the fundamentals of CDC, followed by basic CDC schemes. Then, we review and analyze a number of CDC approaches proposed to reduce the communication costs, mitigate the straggler effects, and guarantee privacy and security. Furthermore, we present and discuss applications of CDC in modern computer networks. Finally, we highlight important challenges and promising research directions related to CDC.

关键词： distributed computing Task analysis Encoding Security Internet of Things Resource management Privacy distributed computing communication minimization straggler effects mitigation security coded distributed computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：