Recently, distributedcomputing systems have become prevalent due to their capability to handle large-scale computations required by emerging machine learning algorithms and signal processing tasks. In real-world scen...
详细信息
ISBN:
(纸本)9781665493802
Recently, distributedcomputing systems have become prevalent due to their capability to handle large-scale computations required by emerging machine learning algorithms and signal processing tasks. In real-world scenarios, these systems often encounter multiple tasks that must be completed within specific deadlines. Furthermore, service providers may offer different levels of service based on their users' subscription tiers. In this study, we focus on the assignment of workers in a heterogeneous coded distributed computing system that comprises multiple masters with distinct subscription tiers. Each master is responsible for a time-sensitive matrix-vector multiplication task that must be completed before a given deadline. The system receives rewards for finishing tasks prior to their deadlines and gives higher priority to tasks associated with higher subscription tiers. Our objective is to devise a worker assignment policy that maximizes the overall reward of the system. To achieve this, we propose a worker assignment policy called "reward greedy." Through simulation results, we demonstrate that our proposed algorithm achieves performance very close to that of a brute-force search while exhibiting significantly lower complexity.
We consider the problems of Private and Secure Matrix Multiplication (PSMM) and Fully Private Matrix Multiplication (FPMM), for which matrices privately selected by a master node are multiplied at distributed worker n...
详细信息
We consider the problems of Private and Secure Matrix Multiplication (PSMM) and Fully Private Matrix Multiplication (FPMM), for which matrices privately selected by a master node are multiplied at distributed worker nodes without revealing the indices of the selected matrices, even when a certain number of workers collude with each other. We propose a novel systematic approach to solve PSMM and FPMM with colluding workers, which leverages solutions to a related Secure Matrix Multiplication (SMM) problem where the data (rather than the indices) of the multiplied matrices are kept private from colluding workers. Specifically, given an SMM strategy based on polynomial codes or Lagrange codes, one can exploit the special structure inspired by the matrix encoding function to design private coded queries for PSMM/FPMM, such that the algebraic structure of the computation result at each worker resembles that of the underlying SMM strategy. Adopting this systematic approach provides novel insights in private query designs for private matrix multiplication, substantially simplifying the processes of designing PSMM and FPMM strategies. Furthermore, the PSMM and FPMM strategies constructed following the proposed approach outperform the state-of-the-art strategies in one or more performance metrics including recovery threshold (minimal number of workers the master needs to wait for before correctly recovering the multiplication result), communication cost, and computation complexity, demonstrating a more flexible tradeoff in optimizing system efficiency.
Codes that possess combination property (CP) and zigzag decoding (ZD) simultaneously (CP-ZD) has broad application into edge aided distributed systems, including distributed storage, coded distributed computing (CDC),...
详细信息
Codes that possess combination property (CP) and zigzag decoding (ZD) simultaneously (CP-ZD) has broad application into edge aided distributed systems, including distributed storage, coded distributed computing (CDC), and CDC-structured distributed training. Existing CP-ZD code designs are based on scalar code, where one node stores exactly one encoded packet. The drawback is that the induced overhead is high. In order to significantly reduce the overhead, vector CP-ZD codes are designed, where vector means the number of stored encoded packets in one node is extended from one to multiple. More specifically, in detailed code construction, cyclic shift is proposed, and the shifts are carefully designed for cases that each node stores two, three, and four packets, respectively. Comparisons show that the overhead is reduced significantly.
We consider the problem of evaluating arbitrary multivariate polynomials over a massive dataset, in a distributedcomputing system with a master node and multiple worker nodes. Generalized Lagrange codedcomputing (GL...
详细信息
ISBN:
(纸本)9781665421607;9781665421591
We consider the problem of evaluating arbitrary multivariate polynomials over a massive dataset, in a distributedcomputing system with a master node and multiple worker nodes. Generalized Lagrange codedcomputing (GLCC) codes are proposed to provide robustness against stragglers who do not return computation results in time, adversarial workers who deliberately modify results for their benefit, and information-theoretic security of the dataset amidst possible collusion of workers. GLCC codes are constructed by first partitioning the dataset into multiple groups, and then encoding the dataset using carefully designed interpolation polynomials, such that interference computation results across groups can be eliminated at the master. Particularly, GLCC codes include the state-of-theart Lagrange codedcomputing (LCC) codes as a special case, and achieve a more flexible tradeoff between communication and computation overheads in optimizing system efficiency.
This paper proposes a novel framework based on Lagrange codedcomputing (LCC) for fast and secure offloading of computing tasks in the mobile edge computing (MEC) network. The network is formed by multiple base statio...
详细信息
This paper proposes a novel framework based on Lagrange codedcomputing (LCC) for fast and secure offloading of computing tasks in the mobile edge computing (MEC) network. The network is formed by multiple base stations (BSs) acting as "masters" which offload their computations to edge devices acting as "workers". The framework aims to ensure efficient allocation of computing loads and bandwidths to workers, and providing them with proper incentives to finish their tasks by the specified deadlines. Thus, each master must decide on the amounts of allocated load and bandwidth, and a service fee paid to each worker given that: i) other masters, i.e., BSs, can be privately-owned or controlled by different operators, i.e., they do not communicate/coordinate their decisions with the master;ii) workers are heterogeneous non-dedicated edge devices with constrained and nondeterministic computing resources. As such, masters compete for the best workers in a stochastic and partially-observable environment. To describe interactions between masters and workers, we formulate a new stochastic auction model with contingent values of bidders, i.e., masters and contingent payments to auctioneers, i.e., workers. To solve the auction, we represent it as a stochastic Bayesian game and develop machine learning algorithms to improve the auction solution.
Edge computing has been a promising approach that allows resource-constrained Internet-of-Things (IoT) devices to offload their computation-intensive tasks to the edge of the networks. Instead of offloading the entire...
详细信息
ISBN:
(纸本)9781728194417
Edge computing has been a promising approach that allows resource-constrained Internet-of-Things (IoT) devices to offload their computation-intensive tasks to the edge of the networks. Instead of offloading the entire computation task to a single edge device, the IoT devices can leverage on the resources of multiple edge devices. In order to improve the performance of the distributed computation tasks, coded distributed computing is proposed to mitigate the straggler effects. However, the edge devices may not have sufficient bandwidth to transmit the computed results to the IoT devices reliably. Hence, we present a deep-learning based auction for the edge devices to buy and utilize bandwidth from the service providers. In particular, the edge devices compete for the bandwidth of the service providers and the service providers allocate bandwidth to the edge devices that value it most while maximizing their revenue. The simulation results show that the deep-learning based auction is optimal as it maximizes the revenue of the service providers while satisfying both properties of individual rationality and incentive compatibility.
Today, modern unmanned aerial vehicles (UAVs) are equipped with increasingly advanced capabilities that can run applications enabled by machine learning techniques, which require computationally intensive operations s...
详细信息
ISBN:
(纸本)9781728181042
Today, modern unmanned aerial vehicles (UAVs) are equipped with increasingly advanced capabilities that can run applications enabled by machine learning techniques, which require computationally intensive operations such as matrix multiplications. Due to computation constraints, the UAVs can offload their computation tasks to edge servers. To mitigate stragglers, coded distributed computing (CDC) based offloading can be adopted. In this paper, we propose an Optimal Task Allocation Scheme (OTAS) based on Stochastic Integer Programming with the objective to minimize energy consumption during computation offloading. The simulation results show that amid uncertainty of task completion, the energy consumption in the UAV network is minimized.
As the amount of data collected for crowdsensing applications increases rapidly due to improved sensing capabilities and the increasing number of Internet of Things (IoT) devices, the cloud server is no longer able to...
详细信息
ISBN:
(纸本)9781728171227
As the amount of data collected for crowdsensing applications increases rapidly due to improved sensing capabilities and the increasing number of Internet of Things (IoT) devices, the cloud server is no longer able to handle the large-scale datasets individually. Given the improved computational capabilities of the edge devices, coded distributed computing has become a promising approach given that it allows computation tasks to be carried out in a distributed manner while mitigating straggler effects, which often account for the long overall completion times. Specifically, by using polynomial codes, computed results from only a subset of devices are needed to reconstruct the final result. However, there is no incentive for the edge devices to complete the computation tasks. In this paper, we present an all-pay auction to incentivize the edge devices to participate in the coded computation tasks. In this auction, the bids of the edge devices are represented by the allocation of their Central Processing Unit (CPU) power to the computation tasks. All edge devices submit their bids regardless of whether they win or lose in the auction. The all-pay auction is designed to maximize the utility of the cloud server by determining the reward allocation to the winners. Simulation results show that the edge devices are incentivized to allocate more CPU power when multiple rewards are offered instead of a single reward.
Federated Learning (FL) is a privacy-preserving collaborative learning approach that trains artificial intelligence (AI) models without revealing local datasets of the FL workers. One of the main challenges is the str...
详细信息
ISBN:
(纸本)9781665406680
Federated Learning (FL) is a privacy-preserving collaborative learning approach that trains artificial intelligence (AI) models without revealing local datasets of the FL workers. One of the main challenges is the straggler effects where the significant computation delays are caused by the slow FL workers. As such, coded Federated Learning (CFL), which leverages coding techniques to introduce redundant computations to the FL server, has been proposed to reduce the computation latency. In order to implement the coding schemes over the FL network, incentive mechanisms are important to allocate the resources of the FL workers and data owners efficiently in order to complete the CFL training tasks. In this paper, we consider a two-level incentive mechanism design problem. In the lower level, the data owners are allowed to support the FL training tasks of the FL workers by contributing their data. To model the dynamics of the selection of FL workers by the data owners, an evolutionary game is adopted to achieve an equilibrium solution. In the upper level, a deep learning based auction is proposed to model the competition among the model owners.
The modern information age is heralded by exciting paradigms that generate a tremendous amount of data, such as health records, financial transactions, and social media user information. As information becomes increas...
详细信息
The modern information age is heralded by exciting paradigms that generate a tremendous amount of data, such as health records, financial transactions, and social media user information. As information becomes increasingly available, distributedcomputing becomes more and more important, especially in information retrieval, search, and computation. The high demand for distributedcomputing brings many new challenges and concerns. This dissertation focuses on privacy, security, and flexibility issues in distributedcomputing from an information-theoretic perspective. Specifically, we study the privacy problem via private information retrieval (PIR) with a focus on the scenarios with available side information and private search. The security and flexibility problems are investigated via coded distributed computing. Two settings for matrix multiplication are studied: the secure multi-party computation and the distributed computation with a flexible number of available servers. PIR allows a user to retrieve one message from databases while preserving the privacy of the desired message index. We investigate the role of side information in PIR, meaning a subset of the messages known by the user. Assume T is the number of possible colluding databases, despite which the privacy of the desired message and the side information should still be maintained. We focus on T-Private Information Retrieval with Private Side Information (TPIR-PSI) and characterize its capacity. A novel achievable scheme is proposed. As a special case obtained by setting T = 1, our result settles the capacity of PIR-PSI, an open problem previously noted by Kadhe et al. We extend our results to the problem of symmetric-TPIR with private side information (STPIR-PSI). Then, we consider private search, where a user searches for all records matching a symbol from the servers, without revealing any information about the queried symbol. Private search is shown to be highly related to PIR with arbitrarily depe
暂无评论