Search

The article presents the discussion on paradigm of virtualization evolving from a virtualized local area network (LAN) and private networks to the solidification of network function virtualization (NFV). Topics include coupled with the pervasive utilization of artificial intelligence (AI) at all network levels; and the Digital Twin (DT) paradigm recently deemed as a promising tool for network design, optimization, management.

This special section focuses on the state-of-the-art technologies on parallel and distributed computing techniques for artificial intelligence (AI), machine learning (ML), and deep learning (DL). AI, ML, and DL can enable computers the ability to learn from a large amount of data and use the learned model to optimize a complex problem or discover rules in a complicated system. AI, ML and DL can be applied to push forward the boundaries for many domains and significantly influence our daily life. [ABSTRACT FROM AUTHOR]

The papers in this special section focus on the use of distributed machine learning for wireless communications. With the emergence of new application scenarios (e.g., real-time and interactive services and Internet of Things) and the fast development of smart terminals, wireless data traffic has increased drastically, and the existing wireless networks cannot completely meet the technical requirements of the next generation mobile communication networks, e.g., 6G. In recent years, machine learning-based methods have been considered as potential technologies for 6G, because in wireless communication systems, key issues behind synchronization, channel estimation, signal detection, and iterative decoding can be solved by well-designed machine learning algorithms. Currently, most wireless network machine learning solutions require the training data and learning process to be centralized in one or more data centers. However, these centralized machine learning methods expose disadvantages, e.g., privacy security, significant signaling overhead, increased implementation complexity, and high latency, which limit their practicality. The wireless networks of the future must make quicker and more reliable decisions at the network edge. [ABSTRACT FROM AUTHOR]

Many datasets including social media data and bibliographic data can be modeled as graphs. Clustering such graphs is able to provide useful insights into the structure of the data. To improve the quality of clustering, node attributes can be taken into account, resulting in attributed graphs. Existing attributed graph clustering methods generally consider attribute similarity and structural similarity separately. In this paper, we represent attributed graphs as star-schema heterogeneous graphs, where attributes are modeled as different types of graph nodes. This enables the use of personalized pagerank (PPR) as a unified distance measure that captures both structural and attribute similarities. We employ DBSCAN for clustering, and we update edge weights iteratively to balance the importance of different attributes. The rapidly growing volume of data nowadays challenges traditional clustering algorithms, and thus, a distributed method is required. Hence, we adopt a popular distributed graph computing system Blogel, based on which, we develop four exact and approximate approaches that enable efficient PPR score computation when edge weights are updated. To improve the effectiveness of the clustering, we propose a simple yet effective edge weight update strategy based on entropy. In addition, we present a game theory based method that enables trading efficiency for result quality. Extensive experiments on real-life datasets offer insights into the effectiveness and efficiency of our proposals. [ABSTRACT FROM AUTHOR]

This paper formulates a distributed computation problem, where a master asks ${\mathsf N}$ distributed workers to compute a linearly separable function. The task function can be expressed as ${\mathsf K}_{\mathrm{ c}}$ linear combinations of ${\mathsf K}$ messages, where each message is a function of one dataset. Our objective is to find the optimal tradeoff between the computation cost (number of uncoded datasets assigned to each worker) and the communication cost (number of symbols the master must download), such that from the answers of any ${\mathsf N}_{\mathrm{ r}}$ out of ${\mathsf N}$ workers the master can recover the task function with high probability, where the coefficients of the ${\mathsf K}_{\mathrm{ c}}$ linear combinations are uniformly i.i.d. over some large enough finite field. The formulated problem can be seen as a generalized version of some existing problems, such as distributed gradient coding and distributed linear transform. In this paper, we consider the specific case where the computation cost is minimum, and propose novel achievability schemes and converse bounds for the optimal communication cost. Achievability and converse bounds coincide for some system parameters; when they do not match, we prove that the achievable distributed computing scheme is optimal under the constraint of a widely used ‘cyclic assignment’ scheme on the datasets. Our results also show that when ${\mathsf K}= {\mathsf N}$ , with the same communication cost as the optimal distributed gradient coding scheme proposed by Tandon et al. from which the master recovers one linear combination of ${\mathsf K}$ messages, our proposed scheme can let the master recover any additional ${\mathsf N}_{\mathrm{ r}}-1$ independent linear combinations of messages with high probability. [ABSTRACT FROM AUTHOR]

This paper studies the distributed linearly separable computation problem, which is a generalization of many existing distributed computing problems such as distributed gradient coding and distributed linear transform. A master asks ${\mathsf {N}}$ distributed workers to compute a linearly separable function of ${\mathsf {K}}$ datasets, which is a set of ${\mathsf {K}}_{\mathrm{ c}}$ linear combinations of ${\mathsf {K}}$ equal-length messages (each message is a function of one dataset). We assign some datasets to each worker in an uncoded manner, who then computes the corresponding messages and returns some function of these messages, such that from the answers of any ${\mathsf {N}}_{\mathrm{ r}}$ out of ${\mathsf {N}}$ workers the master can recover the task function with high probability. In the literature, the specific case where ${\mathsf {K}}_{\mathrm{ c}}=1$ or where the computation cost is minimum has been considered. In this paper, we focus on the general case (i.e., general ${\mathsf {K}}_{\mathrm{ c}} $ and general computation cost) and aim to find the minimum communication cost. We first propose a novel converse bound on the communication cost under the constraint of the popular cyclic assignment (widely considered in the literature), which assigns the datasets to the workers in a cyclic way. Motivated by the observation that existing strategies for distributed computing fall short of achieving the converse bound, we propose a novel distributed computing scheme for some system parameters. The proposed computing scheme is optimal for any assignment when ${\mathsf {K}}_{\mathrm{ c}}$ is large and is optimal under the cyclic assignment when the numbers of workers and datasets are equal or ${\mathsf {K}}_{\mathrm{ c}}$ is small. In addition, it is order optimal within a factor of 2 under the cyclic assignment for the remaining cases. [ABSTRACT FROM AUTHOR]

Large software defined networks use a cluster of distributed controllers to process flow requests from a massive number of switches. To cope with traffic dynamics, this paper studies a new problem of how to improve the residual capacity available at the controllers to handle request bursts experienced at the switches. While the total residual capacity is a constant under a given total capacity of all controllers and a given total workload from all switches, this paper considers the residual capacity available to each individual switch, which depends on how the switches are mapped to the controllers for management. We focus on how to maximize the minimum residual capacity available to any switch. The prior work either provides poor residual capacity or incurs heavy synchronization overhead by simulation results. This paper proposes a new method called indirect multi-mapping that achieves both high residual capacity and low synchronization cost. We formally define a non-linear integer optimization problem for max-min residual capacity under indirect multi-mapping. We then approximate the problem as two sub-problems: switch-controller mapping selection and weight assignment for each switch-controller mapping. We solve these sub-problems and formally analyze their approximate factor. We implement the proposed solution on an SDN testbed for experimental studies and use simulations for large-scale investigation. Our evaluation shows that indirect multi-mapping improves the minimum residual capacity by 49.8% on average and reduces the synchronization cost by 41.9-60.3% on average when compared with the alternatives. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Multimodal path queries over transportation networks are receiving increasing attention due to their widespread applications. A multimodal path query consists of finding multimodal journeys from source to destination in transportation networks, including unrestricted walking, driving, cycling, and schedule-based public transportation. Transportation networks are generally continent-sized. This characteristic highlights the need for parallel computing to accelerate multimodal path queries. Meanwhile, transportation networks are often fragmented and distributively stored on different machines. This situation calls for exploiting parallel computing power for these distributed systems. Therefore, in this paper, we study distributed multimodal path (DMP) queries over large transportation networks. We develop algorithms to explore parallel computation. When evaluating a DMP query $Q$ Q on a distributed multimodal graph $Gmult$ G m u l t , we show that the algorithms possess the following performance guarantees, irrespective of how $Gmult$ G m u l t is fragmented and distributed: (1) each machine is visited only once; (2) the total network traffic is determined by the size of $Q$ Q and the fragmentation of $Gmult$ G m u l t ; (3) the response time is decided by the largest fragment of $Gmult$ G m u l t ; and (4) the algorithm is parallel scalable. Using real-life and synthetic data, we experimentally verify that the algorithms are scalable on large graphs. [ABSTRACT FROM AUTHOR]

Matrix multiplication is a fundamental building block in various distributed computing algorithms. In order to multiply large matrices, it is common practice to distribute the computation into multiple tasks running on different nodes. In order to tolerate stragglers among such nodes, various coding schemes have been proposed by adding additional coded tasks. However, most existing coding schemes for matrix multiplication are constructed for only one matrix multiplication, while batch matrix multiplication is common in large-scale distributed computing workloads. In this paper, we propose Rook Coding (RC), a novel polynomial-based coding framework for computing the multiplication of $n$ pairs of matrices in batch. Designed to achieve lower encoding time in practice, we construct RC as polynomials of much simpler forms than existing coding schemes for batch matrix multiplication, achieving a recovery threshold of $O(n^{\log _{2} ~3})$. Compared to existing coding schemes, RC achieves a lower encoding complexity in practice, because of its simpler forms in the encoding polynomials. Through extensive experiments, we show that RC can save the time of the whole job thanks to its low overhead of encoding. [ABSTRACT FROM AUTHOR]

Mission-critical Internet-of-Things (IoT) applications require communication interfaces that provide ultra-reliability and low latency. Acquiring knowledge regarding the number of active devices and their latency-reliability requirements becomes essential to optimize resource allocation in heterogeneous networks. Due to the inherent heavy computation overheads, the conventional centralized decision-making approaches result in large latency. The distributed computing and device-level prediction of network parameters can play a significant role in designing mission-critical IoT applications operating in dynamic environments. This paper considers the medium access control (MAC) layer of heterogeneous networks employing a framed-ALOHA-based restricted transmission strategy to enhance reliability. We present a statistical learning-based device-level network exploration mechanism in which end-devices use their transmission history to predict different network parameters. The IoT devices share the learned parameters with the base station (BS) to identify different groups presented in the network. The simulation results show that the mean square error (MSE) in predicting different network parameters can be reduced by increasing the history window size. In this regard, the optimal size of the history window under the given accuracy constraints is also determined. We demonstrate that the proposed device-level network load prediction mechanism is more robust as compared to the BS-centered approach. [ABSTRACT FROM AUTHOR]

In three-phase AC/DC hybrid networked microgrids (NMGs), the operational limits of AC/DC interconnected converters and distributed generator (DG) interface inverters increase the non-convexity of the power flow model, and conventional distributed power flow (DPF) algorithms based on heuristic rule may encounter convergence problems when processing limit. This paper proposed a fully DPF calculation method that can robustly handle the non-smooth reactive power limits of converters and non-smooth voltage regulation of step voltage regulators, also reducing the model dependence on the initial values. In this algorithm, the non-smooth constraints were converted into smooth functions, and based on a bi-level augmented Lagrangian alternating direction inexact Newton (ALADIN) method with the second-order convergence rate the original DPF problem was transformed into the problem of distributed step increment optimization. Accurate power flow results can be obtained by exchanging boundary information between microgrids, and the proposed algorithm can converge rapidly with step increment optimization at the second level. Numerical experiments demonstrated the accuracy, convergence, and efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

The increasing prevalence of massive datasets makes the outsourcing of storage and computation tasks to distributed servers a necessity. This raises a number of concerns regarding the security and integrity of stored information, the privacy of accessing desired information, the communication overhead of distributed systems, the latency, reliability, and complexity of distributed computing, and privacy in distributed training and learning systems. Recent breakthroughs from coding, communication, and information-theoretic perspectives have opened up exciting new research avenues for these topics. There are many theoretical and practical open problems. This Special Issue is dedicated to communication theory, coding theory, information theory, signal processing, and networking aspects of privacy in information retrieval, privacy in coded computing over distributed servers, and privacy in distributed learning. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Distributed linearly separable computation, where a user asks some distributed servers to compute a linearly separable function, was recently formulated by the same authors and aims to alleviate the bottlenecks of stragglers and communication cost in distributed computation. The data center assigns a subset of input datasets to each server in an uncoded manner, and each server computes some coded packets on the assigned datasets, which are then sent to the user. The user should recover the task function from the answers of a subset of servers, such that the effect of stragglers could be tolerated. In this paper, we formulate a novel secure framework for this distributed linearly separable computation, where we aim to let the user only retrieve the desired task function without obtaining any other information about the input datasets, even if it receives the answers of all servers. In order to preserve the security of the input datasets, some common randomness variable independent of the datasets should be introduced into the transmission. We show that any non-secure linear-coding based computing scheme for the original distributed linearly separable computation problem, can be made secure without increasing the communication cost (number of symbols the user should receive). Then we focus on the case where the computation cost of each server (number of datasets assigned to each server) is minimum and aim to minimize the size of the randomness variable (i.e., randomness size) introduced in the system while achieving the optimal communication cost. We first propose an information theoretic converse bound on the randomness size. We then propose secure computing schemes based on two well-known data assignments, namely fractional repetition assignment and cyclic assignment. These schemes are optimal subject to using these assignments. Motivated by the observation of the general limitation of these two schemes on the randomness size, we propose a computing scheme with novel assignment, which strictly outperforms the above two schemes. Some additional optimality results are also obtained. [ABSTRACT FROM AUTHOR]

Distributed computing enables parallel execution of smaller tasks that make up a large computing job. Its purpose is to reduce the job completion time. However, random fluctuations in task service times lead to straggling tasks with long execution times. Redundancy provides diversity that allows job completion when only a subset of redundant tasks is executed, thus removing the dependency on the straggling tasks. Under constrained resources (here, a fixed number of parallel servers), increasing redundancy reduces the available resources for parallelism. In this paper, we characterize the diversity vs. parallelism trade-off and identify the optimal strategy among replication, coding, and splitting, which minimizes the expected job completion time. We consider three common service time distributions and establish three models that describe the scaling of these distributions with the task size. We find that different distributions with different scaling models operate optimally at different redundancy levels, thus requiring very different code rates. [ABSTRACT FROM AUTHOR]

Recently, with the maturity of edge-cloud computing and the large amount of data generated in the edge, we have witnessed an increasing number of applications conducting collaborative learning and data analytics in networked edge systems. On the other end of the spectrum, there are also fast-growing concerns on privacy on using the data in the edge, which belong to diverse owners. Federated learning (FL) and federated analytics (FA), coined together as federated optimizations by Google, are new distributed computing techniques to address such a mismatch. In federated optimization, raw data are kept local and only the focused updates (weights or data insights) generated from local analytics are sent to a cloud server for result aggregation. [ABSTRACT FROM AUTHOR]

As an emulous alternative to deep neural networks, Deep Forest emerges with features like low complexity, fewer hyper-parameters, and good robustness, which are predominantly desired in distributed computing applications and ecosystems. Recently, an efficient distributed Deep Forest system, named ForestLayer, was proposed, designing a fine-grained sub-Forest-based task-parallel algorithm to improve the parallel computing efficiency of Deep Forest. However, the sub-Forest splitting of ForestLayer is static and one-off without adaptability to the computing environment, nevertheless, the size of splitting granularity has a significant impact on the system performance. To further improve the computing efficiency and scalability of the distributed Deep Forest, in this paper, we propose a novel distributed Deep Forest algorithm, named BLB-gcForest (Bag of Little Bootstraps-gcForest), which augments the gcForest (multi-Grained Cascade Forest) approach for constructing Deep Forest. BLB-gcForest carries out parallel computation for each tree in sub-Forests at a finer parallel granularity and integrates with the Bag of Little Bootstraps (BLB) mechanism to reduce massive transmitted feature instances for Cascade Forest Layers, utterly improving both computation efficiency and communication efficiency. Moreover, to solve the problem of the forest splitting granularity, we further design an adaptive sub-Forest splitting algorithm to ensure the maximum resource utilization for parallel computation of each sub-Forest. Experimental results on four well-known large-scale datasets, namely YEAST, LETTER, MNIST, CIFAR10, show that the training efficiency of BLB-gcForest achieves up to 20.3x and 1.64x speedups compared with the state-of-the-art gcForest and ForestLayer, respectively while guaranteeing higher accuracy and better robustness [ABSTRACT FROM AUTHOR]

Coded distributed computing (CDC) is an efficient method to reduce the communication load in general distributed computing frameworks such as MapReduce. In these systems, one usually needs to split the data set into disjoint files and design several output functions to complete a computational task. Li et al. provided some CDC schemes achieving optimal communication load. However, as the number of computing nodes increases, the numbers of input files and output functions of such schemes grow too fast to be applied in practice. In this paper, several infinite families of cascaded CDC schemes, where each output function is computed multiple times, are constructed by taking advantage of symmetric designs. Most importantly, the numbers of input files and output functions of each new scheme are linear with the number of computing nodes and the communication load of each new scheme approximates to that of the CDC scheme derived by Li et al. when the number of nodes becomes large. [ABSTRACT FROM AUTHOR]

Gossip protocols are popular methods for average consensus problems in distributed computing. We prove new convergence guarantees for a variety of such protocols, including path, clique, and synchronous pairwise gossip. These arise by exploiting the connection between these protocols and the block randomized Kaczmarz method for solving linear systems. Moreover, we extend existing convergence results for block randomized Kaczmarz to allow for a more general choice of blocks, rank-deficient systems, and provide a tighter convergence rate guarantee. Previous results for block randomized Kaczmarz assumed blocks formed a paving of the systems; our analysis, contrary to the title of our paper, generalizes to a broader class of blocks that we call coverings. We furthermore apply this analysis to inconsistent consensus models and obtain similar guarantees. An extensive empirical analysis of these methods is provided for a variety of synthetic and real networks. [ABSTRACT FROM AUTHOR]

We propose a novel Federated Edge Network Utility Maximization (FEdg-NUM) architecture for solving a large-scale distributed network utility maximization (NUM) problem. In FEdg-NUM, clients with private utilities communicate to a peer-to-peer network of edge servers. This represents a departure from the classical distributed NUM master-slave configuration and enables distributed computing harnessing local communications. Compared to a solution using cloud synchronization via Ring AllReduce, we prove that our federated edge computing model has shorter run-time in the presence of network congestion, thanks to its configuration and its ability to make progress in the presence of intermittent links. The paper studies its convergence and run-time performance both analytically and numerically, and illustrates several possible networking applications. [ABSTRACT FROM AUTHOR]

Current spatial-keyword publish/subscribe systems need to handle spatial-keyword skyline queries over geo-textual streams to continuously obtain good results. The skyline queries in such systems face two main problems: (1) query problems, because the powerful query capability is required for the strict limit of the response time and the large number of items concerned by the users, and (2) scalability issue, because millions of active users are maintained simultaneously with many network-connected machines. Unfortunately, the current approach is towards static data. Thus, this paper first proposes a distributed skyline query processing framework. Then, we optimize the skyline computing by introducing MF-R $^t$ t -tree, which is an update-efficient and space-saving indexing structure and a fast approach for processing a continuous spatial-keyword skyline query called $eager^*$ e a g e r * . Finally, a spatial and textual signature-based communication optimization method is proposed to support scalability. The experimental results indicate that (1) MF-R $^t$ t -tree can significantly reduce update costs, while maintaining a low storage cost, and a query performance comparable to IL-Quadtree, (2) $eager^*$ e a g e r * can averagely accelerate 79.72 × faster than the method based on BNL, (3) the communication optimization method significantly reduces the communication cost, and (4) the distributed framework can efficiently support large-scale skyline queries. [ABSTRACT FROM AUTHOR]

Distributed computing systems, such as Hadoop, have been widely studied and used for executing and analyzing large data. In this paper, we investigate an emerging resource allocation problem for wireless distributed computing systems consisting of multifunctional nodes in charge of both numerical computation and wireless communication with master nodes. We focus on a computation power consumption model based on CMOS devices and a communication power consumption model involving multiple antenna transceivers against mutual interference. We present a joint optimization problem for workload scheduling and power allocation for achieving maximum computational speed under total power constraint. We simplify the joint optimization into two sub-problems. For workload scheduling as an integer programming sub-problem, we relax the integer constraint and establish the equivalence between relaxed and original problems. For the power allocation sub-problem, we maximize a difference of convex functions by utilizing the concave-convex procedure. We prove our proposed algorithm to converge to a stationary point of the original program. Simulation results confirm the efficiency and near-optimal performance of our proposed algorithms. [ABSTRACT FROM AUTHOR]

Device-to-device (D2D) communications is expected to be a critical enabler of distributed computing in edge networks at scale. A key challenge in providing this capability is the requirement for judicious management of the heterogeneous communication and computation resources that exist at the edge to meet processing needs. In this paper, we develop an optimization methodology that considers the network topology jointly with device and network resource allocation to minimize total D2D overhead, which we quantify in terms of time and energy required for task processing. Variables in our model include task assignment, CPU allocation, subchannel selection, and beamforming design for multiple-input multiple-output (MIMO) wireless devices. We propose two methods to solve the resulting non-convex mixed integer program: semi-exhaustive search optimization, which represents a “best-effort” at obtaining the optimal solution, and efficient alternate optimization, which is more computationally efficient. As a component of these two methods, we develop a novel coordinated beamforming algorithm which we show obtains the optimal beamformer for a common receiver characteristic. Through numerical experiments, we find that our methodology yields substantial improvements in network overhead compared with local computation and partially optimized methods, which validates our joint optimization approach. Further, we find that the efficient alternate optimization scales well with the number of nodes, and thus can be a practical solution for D2D computing in large networks. [ABSTRACT FROM AUTHOR]

Density Peaks (DP) Clustering organizes data into clusters by finding peaks in dense regions. This involves computing density ($\rho$ ρ ) and distance ($\delta$ δ ) of every point. As such, though DP has been very effective in producing high quality clusters, their complexity is O($N^2$ N 2 ) where $N$ N is the number of data points. In this paper, we propose a fast distributed density peaks clustering algorithm, FDDP, based on the z-value index. In FDDP, we first employ the z-value index to map multi-dimensional data points into one dimensional space, and then range-partition the data according to the z-value to balance the load across the processing nodes. We ensure minimal overlapping range to handle computations at the boundary points. We also propose FC, an efficient algorithm that employs a forward computing strategy to calculate $\rho$ ρ linearly. Additionally, we propose another algorithm, CB, which uses a caching and efficient searching strategy to compute $\delta$ δ . Moreover, FDDP is able to reduce the time complexity from $O(N^2)$ O (N 2) to $O(N\cdot log(N))$ O (N · l o g (N)) . We provide a theoretical analysis of FDDP and evaluated FDDP empirically. Our experimental results show that FDDP outperforms the state-of-the-art algorithms significantly. [ABSTRACT FROM AUTHOR]

Distributed computing has become one of the most important frameworks in dealing with large computation tasks. In this paper, we propose a systematic construction of coded computing schemes for MapReduce-type distributed systems. The construction builds upon placement delivery arrays (PDA), originally proposed by Yan et al. for coded caching schemes. The main contributions of our work are three-fold. First, we identify a class of PDAs, called Comp-PDAs, and show how to obtain a coded computing scheme from any Comp-PDA. We also characterize the normalized number of stored files (storage load), computed intermediate values (computation load), and communicated bits (communication load), of the obtained schemes in terms of the Comp-PDA parameters. Then, we show that the performance achieved by Comp-PDAs describing Maddah-Ali and Niesen’s coded caching schemes matches a new information-theoretic converse, thus establishing the fundamental region of all achievable performance triples. In particular, we characterize all the Comp-PDAs achieving the pareto-optimal storage, computation, and communication (SCC) loads of the fundamental region. Finally, we investigate the file complexity of the proposed schemes, i.e., the smallest number of files required for implementation. In particular, we describe Comp-PDAs that achieve pareto-optimal SCC triples with significantly lower file complexity than the originally proposed Comp-PDAs. [ABSTRACT FROM AUTHOR]

The advent of online applications such as social networks has led to an unprecedented scale of data and complex relationships among data. Hypergraphs are introduced to represent complex relationships that may involve more than two entities. A hypergraph is a generalized form of a graph, where edges are generalized to hyperedges. Each hyperedge may consist of any number of vertices. The flexibility of hyperedges also brings challenges in distributed hypergraph processing. In particular, a hypergraph is more difficult to be partitioned and distributed among $k$ k workers with balanced partitions. In this paper, we propose to convert a hypergraph into an intersection graph before partitioning by leveraging the inherent shared relationships among hypergraphs. We explore the intersection graph construction method and the corresponding partition strategy which can achieve the goal of evenly distributing vertices and hyperedges across workers, while yielding a significant communication reduction. We also design a distributed processing framework named $Hyraph$ H y r a p h that can directly run hypergraph analysis algorithms on our intersection graphs. Experimental results on real datasets confirm the effectiveness of our techniques and the efficiency of the $Hyraph$ H y r a p h framework. [ABSTRACT FROM AUTHOR]

Media production is facing tremendous challenges during processing and transmission, due to large data volume, high computational complexity and real-time transmission requirement. Hence, more and more media servers tend to spread media content in a distributed manner, over e.g., cloud platform or edge computing nodes, which are closer to client side and/or have adequate computing capacity. Benefiting from cloud or edge computing, users can receive various media service with high quality and low latency. Network-based Media Processing (NBMP) established by International Organization for Standardization (ISO)/International Electrotechnical Commission (IEC) standard organization-Moving Picture Experts Group (MPEG), is one of these representative distributed architectures, which has attracted a wide range of attention. This paper focuses on emerging cloud and edge computation for media production to highlight the necessity of adopting a distributed computing framework. We take NBMP architecture as an example, and introduce the basic components and workflow in distributed processing frameworks. Moreover, we also provide related application instances based on NBMP with the hope of promoting future development of cloud and edge computation. [ABSTRACT FROM AUTHOR]

The performance of distributed computing is restricted by the slowest worker nodes, known as stragglers, in the system. Coded computation has emerged as an efficient technique to mitigate the straggler effects in distributed computing. Most existing works only considered the computation straggler for single-hop networks. However, in multi-hop networks, the straggler effects will occur not only on worker nodes but also on relay nodes. In this paper, we consider a heterogeneous multi-hop network. The nodes in the network are heterogeneous, i.e., their computation capacities and transmission capacities are different. We propose a hierarchical coding scheme for such a network. Firstly, we reorganize it into a hierarchical network containing multiple layers. Each layer in the network consists of several groups. Then, a new hierarchical coding scheme is proposed, where coding is applied to each group to mitigate the stragglers. By taking both the computation time and transmission time into consideration, the overall task completion time is derived. To improve the performance of the network, heterogeneous hierarchical coded computation (HHCC) algorithm is proposed to provide an asymptotically optimal task allocation strategy. Compared with existing uniform uncoded, load balanced uncoded, and heterogeneous coded matrix multiplication schemes, HHCC has significant improvement. [ABSTRACT FROM AUTHOR]

Considering the increasing demand for large-scale MapReduce distributed computing, coded distributed computing (CDC) has become a promising technology to reduce the significant bottleneck of MapReduce computation. Despite its importance, most of the works on CDC have assumed homogeneous environments, where the nodes have the same storage, computing, and communication capacities. However, since many practical scenarios involve heterogeneous environments, heterogeneous CDC design is highly demanded to reduce communication load. Under consideration of full heterogeneity among workers, this paper addresses the joint design of function assignment and coded shuffling to reduce communication load effectively. We first devise a new embedded index coding (EIC) solution for the device-to-device (D2D) environment and prove its optimality. By extending our novel approach, we propose the optimal shuffling design for the MapReduce framework. Then, we figure out the optimal function assignment with the optimal shuffling design. On account of the prohibitive complexity, we propose an efficient greedy search algorithm and analyze how much performance the proposed scheme can guarantee. Numerical simulations show that our proposed algorithm provides the near-optimal communication load with a considerable complexity reduction, while we observe that the function assignment design is vital for heterogeneous CDC by comparing with the well-designed file allocation design. [ABSTRACT FROM AUTHOR]

Currently, the highly dynamic fog computing resource requirements introduced by the diverse services of the Internet of Things (IoT) result in an imbalance between computing resource providers and consumers. However, current computing resource scheduling schemes cannot cognize the dynamic resources available and do not possess decision-making or management capabilities, which leads to inefficient use of computing resources and a decreased quality of service (QoS). Balancing computing resources cognitively at the IoT edge remains unresolved. In this paper, a cognition-centric fog computing resource balancing (CFCRB) scheme is proposed for edge intelligence-enabled IoT. First, we propose a cognitive balance architecture with a cognition plane, which includes service demand monitoring, policy processing and knowledge storage of cognitive fog resources. Second, we propose the fog functions structure with sensing, interaction and learning functionalities, realizing the knowledge-based proactive discovery and dynamic orchestration of resource sharing nodes. Finally, a distributed edge learning algorithm is proposed to construct knowledge of the balance between computing resource helpers and requesters in cognitive fogs, which is further proved with mathematics. The simulation results indicate the efficiency of the proposed scheme. [ABSTRACT FROM AUTHOR]

Currently, the world is experiencing the rapid spread of Coronavirus Disease 2019 (COVID-19). Since the epidemic continues to take a devastating impact on the society, economy, and healthcare, the real-time detection of COVID-19 is essential for fast and cost-effective diagnosis services. Fortunately, deep learning (DL), as a promising technology, enables the COVID-19 diagnosis services on chest X-ray (CXR) images. The training task of DL model is generally implemented at the centralized cloud. However, due to the geo-distributed data sources and the transmission of large amounts of raw data to the centralized cloud, the transmission latency becomes a bottleneck of the COVID-19 diagnosis model training. In this paper, we propose a Distributed COVID-19 detection model training method on CXR images with edge-cloud collaboration, named DisCOV. Specifically, to improve the training efficiency and guarantee the model accuracy, a distributed lightweight model-based training algorithm is designed with the cooperation of edge computing and cloud computing. In addition, a resource allocation algorithm is developed during the training to jointly minimize the time cost and energy consumption. Extensive experiments based on real-world CXR image datasets demonstrate that DisCOV is better performed and more promising than the existing baselines. [ABSTRACT FROM AUTHOR]

For direction-of-arrival (DOA) estimation of heterogeneous wideband sources, we propose a new adaptive space-frequency joint processing algorithm. The algorithm is implemented in the sparse Bayesian learning (SBL) DOA framework, which is named as ASF-SBL algorithm in this paper. The traditional SBL-based DOA methods suffer from the problem of erroneous DOA estimation due to the structural mismatch between the invariant prior and the sparse coefficients. To solve this problem, the ASF-SBL algorithm employs a new space-frequency correlation prior model that can be adaptively changed to fit heterogeneous DOA scenarios. Specifically, nine alternative space-frequency structural patterns are constructed to represent the joint space-frequency characteristics of spatial sparse signals. By evaluating the space-frequency correlation of the sparse coefficients updated in each iteration under SBL framework, a suitable pattern is selected from the nine choices to determine the adaptive prior of each coefficient. This adaptive method leads to accurate DOA estimation in different wideband sources scenarios. In addition, we introduce a distributed processing method to extend the ASF-SBL algorithm to two-dimensional DOA estimation. This extension is achieved by decoupling the DOA estimation into two one-dimensional estimations. The decoupling avoids the problems of a huge redundant dictionary and excessive computational complexity caused by the combination of azimuth and elevation angles. Numerical simulations show that the ASF-SBL algorithm is superior to existing algorithms in DOA estimation of heterogeneous sources. [ABSTRACT FROM AUTHOR]

In smart cities, more and more government departments will make use of live analytics of videos from surveillance cameras in their tasks, such as vehicle traffic monitoring and criminal detection. Obviously, it is costly for each individual department to deploy its own infrastructure, i.e., cameras and analytics system. In this paper, we consider a scenario in which a city deploys an infrastructure and departments submit requests to access and analyze videos for their own purposes. The live analytics of massive streams is computation-intensive and the tasks might be latency-critical, which makes scheduling massive streams to optimize all tasks an essential and challenging work. We exploit an end-edge-cloud architecture and propose an adaptive system to schedule the massive camera streams and tasks, which considers all factors affecting the computation and networking resource consumption, e.g., sharing of model computation, video quality, model partition, and task placement. Particularly, the resource consumption of Faster R-CNN + ResNet101 under each partition scheme is profiled for the first time and we notice the partition must be used together with lossless compression techniques to be beneficial. Furthermore, sometimes tasks might be required to migrate because the scheduling decision made by the system changes to adapt to the changing resource supply and demand. In order to avoid the performance degradation during migration, we propose a non-destructive migration scheme and implement it in the system. Simulations demonstrate our system achieves a total utility close to the maximum and our analytics system performs better than state-of-the-art solutions. [ABSTRACT FROM AUTHOR]

This paper focuses on mitigating the impact of stragglers in distributed learning system. Unlike the existing results designated for a fixed number of stragglers, we develop a new scheme called Adaptive Gradient Coding (AGC) with flexible communication cost for varying number of stragglers. Our scheme gives an optimal tradeoff between computation load, straggler tolerance and communication cost by allowing workers to send multiple signals sequentially to the master. In particular, it can minimize the communication cost according to the unknown real-time number of stragglers in practical environments. In addition, we present a Group AGC (G-AGC) by combining the group idea with AGC to resist more stragglers in some situations. The numerical and simulation results demonstrate that our adaptive schemes can achieve the smallest average running time. [ABSTRACT FROM AUTHOR]

In the era of digitized images, the goal is to extract information from them and create new knowledge thanks to Computer Vision techniques, Machine Learning and Deep Learning. This enables the use of images for early diagnosis and subsequent treatment of a wide range of diseases. In the dermatological field, deep neural networks are used to distinguish between melanoma and non-melanoma images. In this paper, we have underlined two essential points of melanoma detection research. The first aspect considered is how even a simple modification of the parameters in the dataset determines a change of the accuracy of classifiers. In this case, we investigated the Transfer Learning issues. Following the results of this first analysis, we suggest that continuous training-test iterations are needed to provide robust prediction models. The second point is the need to have a more flexible system architecture that can handle changes in the training datasets. In this context, we proposed the development and implementation of a hybrid architecture based on Cloud, Fog and Edge Computing to provide a Melanoma Detection service based on clinical and dermoscopic images. At the same time, this architecture must deal with the amount of data to be analyzed by reducing the running time of the continuous retrain. This fact has been highlighted with experiments carried out on a single machine and different distribution systems, showing how a distributed approach guarantees output achievement in a much more sufficient time. [ABSTRACT FROM AUTHOR]

Coded computation has attracted great interests as a promising technique to cope with straggling computing nodes in mobile edge computing (MEC) networks. Contrary to the existing coded computation schemes developed with a fixed network topology, this paper studies a MDS coded computation for random networks. Specifically, we put forth maximum distance separable (MDS) coded task offloading and investigate its MDS coded computing gain by deriving the average successful retrieval probability with stochastic geometry in random wireless edge computing networks, where it encodes the original task into multiple equal and small sized MDS coded sub-tasks and offloads their subset to edge computing nodes for computation. We also identify a tradeoff between the latency in processing a sub-task at an edge node and the minimal number of edge nodes required to retrieve the original task output, according to the size of MDS coded sub-tasks. To efficiently control the tradeoff, we determine the desirable size of MDS coded sub-tasks in a semi-closed form to maximize the average successful retrieval probability for regime 1 and regime 2 networks, which correspond to the cases that communication latency is negligible compared to computation latency and that computation latency is negligible compared to communication latency, respectively, and develop an efficient algorithm with low search complexity for a general environment. Our numerical results reveal that the proposed scheme outperforms the other conventional task offloading schemes such as partial task offloading and replication task offloading in terms of average successful retrieval probability. [ABSTRACT FROM AUTHOR]

Coded computation techniques provide robustness against straggling workers in distributed computing. However, most of the existing schemes require exact provisioning of the straggling behavior and ignore the computations carried out by straggling workers. Moreover, these schemes are typically designed to recover the desired computation results accurately, while in many machine learning and iterative optimization algorithms, faster approximate solutions are known to result in an improvement in the overall convergence time. In this paper, we first introduce a novel coded matrix-vector multiplication scheme, called coded computation with partial recovery (CCPR), which benefits from the advantages of both coded and uncoded computation schemes, and reduces both the computation time and the decoding complexity by allowing a trade-off between the accuracy and the speed of computation. We then extend this approach to distributed implementation of more general computation tasks by proposing a coded communication scheme with partial recovery, where the results of subtasks computed by the workers are coded before being communicated. Numerical simulations on a large linear regression task confirm the benefits of the proposed scheme in terms of the trade-off between the computation accuracy and latency. [ABSTRACT FROM AUTHOR]

Bitcoin is the leading example of a blockchain application that facilitates peer-to-peer transactions without the need for a trusted third party. This paper considers possible attacks related to the decentralized network architecture of Bitcoin. We perform a data driven study of Bitcoin and present possible attacks based on spatial and temporal characteristics of its network. Towards that, we revisit the prior work, dedicated to the study of centralization of Bitcoin nodes over the Internet, through a fine-grained analysis of network distribution, and highlight the increasing centralization of the Bitcoin network over time. As a result, we show that Bitcoin is vulnerable to spatial, temporal, spatio-temporal, and logical partitioning attacks with an increased attack feasibility due to the network dynamics. We verify our observations through data-driven analyses and simulations, and discuss the implications of each attack on the Bitcoin network. We conclude with suggested countermeasures. [ABSTRACT FROM AUTHOR]

The local model poisoning attack is an attack to manipulate the shared local models during the process of distributed learning. Existing defense methods are passive in the sense that they try to mitigate the negative impact of the poisoned local models instead of eliminating them. In this paper, we leverage the new federated analytics paradigm, to develop a proactive defense method. More specifically, federated analytics is to collectively carry out analytics tasks without disclosing local data of the edge devices. We propose a Federated Anomaly Analytics enhanced Distributed Learning (FAA-DL) framework, where the clients and the server collaboratively analyze the anomalies. FAA-DL firstly detects all the uploaded local models and splits out the potential malicious ones. Then, it verifies each potential malicious local model with functional encryption. Finally, it removes the verified anomalies and aggregates the remaining to produce the global model. We analyze the FAA-DL framework and show that it is accurate, robust, and efficient. We evaluate FAA-DL by training classifiers on MNIST and Fashion-MNIST under various local model poisoning attacks. Our experiment results show FAA-DL improves the accuracy of the learned global model under strong attacks up to 6.90 times and outperforms the state-of-the-art defense methods with a robustness guarantee. [ABSTRACT FROM AUTHOR]

The development of smart vehicles and rich cloud services have led to the emergence of vehicular edge computing. To perform the distributed computation tasks efficiently, Coded Distributed Computing (CDC) was proposed to reduce communication costs and mitigate the straggler effects through the use of coding techniques. In this paper, we propose a double auction mechanism to allocate the resources of the edge servers to the vehicles in order to complete the CDC tasks. Specifically, the vehicles use the PolyDot codes to manage the tradeoff between communication costs and recovery threshold. Given the requirements of various vehicles, the double auction mechanism matches the edge servers with the required resources to the vehicles. Besides, the double auction mechanism also determines the prices that the vehicles need to pay for the resources of the edge servers. The analyses show that the double auction mechanism satisfies the properties of individual rationality, incentive compatibility and budget-balance. From the simulation, the utility of auctioneer increases when the number of vehicles and edge servers increases. [ABSTRACT FROM AUTHOR]

Temporal decomposition is a potential approach to relieve the computation cost of power system multi-interval scheduling problems, such as economic dispatch. In this form of decomposition, the considered scheduling horizon is partitioned into several subhorizons. A subproblem is formulated for each subhorizon, and a distributed optimization algorithm strategy is used to coordinate subproblems. The main existing challenge is decomposing the scheduling horizon to gain the most time saving from distributed computing. This paper serves as an extension to our previous work and presents a machine learning-aided temporal decomposition strategy to partition a scheduling horizon optimally. We have found that the load profile, known before solving economic dispatch, significantly affects the best number of subhorizons. We have used load profiles as inputs to a learner whose goal is to assign a temporal decomposition class to each load profile. Possible decomposition classes are divisors of the considered scheduling horizon. Thus, the proposed learning procedure is a multiclass classification. We have selected Extreme Gradient Boosting that is a tree-based classification learner. Simulation results using real-world load profiles show the promising performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Coding theoretic approaches have been developed to significantly reduce the communication load in modern distributed computing system. In particular, coded distributed computing (CDC) introduced by Li et al. can efficiently trade computation resources to reduce the communication load in MapReduce like computing systems. For the more general cascaded CDC, Map computations are repeated at $r$ nodes to significantly reduce the communication load among nodes tasked with computing $Q$ Reduce functions $s$ times. In this paper, we propose a novel low-complexity combinatorial design for cascaded CDC which 1) determines both input file and output function assignments, 2) requires significantly less number of input files and output functions, and 3) operates on heterogeneous networks where nodes have varying storage and computing capabilities. We provide an analytical characterization of the computation-communication tradeoff, from which we show the proposed scheme can outperform the state-of-the-art scheme proposed by Li et al. for the homogeneous networks. Further, when the network is heterogeneous, we show that the performance of the proposed scheme can be better than its homogeneous counterpart. In addition, the proposed scheme is optimal within a constant factor of the information theoretic converse bound while fixing the input file and the output function assignments. [ABSTRACT FROM AUTHOR]

Most current research on commonly used distributed computing frameworks neglects the difficulty of learning these frameworks. These commonly used distributed computing frameworks are designed for professionals, and users must understand them well to use them for calculation tasks. In order to solve the challenging balance problem between versatility and user learning difficulty, a new distributed computing system is proposed. The design of this system is based on the idea of divide and conquer in distributed computing. The paper uses Netty, Zookeeper, Hadoop Distributed File System (HDFS) and other tools to implement the system functions. Firstly, the paper analyzes the research status of distributed computing frameworks at home and abroad; Then, according to the idea of divide and conquer, the paper uses Netty to implement the basic architecture of the system, uses Zookeeper and Netty to implement relevant distributed mechanisms, uses HDFS as the distributed storage, designs and implements a Task-Oriented General-Purpose (TOGP) distributed computing system, TOGP; Finally, the paper intensely studies the task scheduling problem of the system, proposes a scheduling algorithm, Node Processing Capacity and Distributed Lock Task Scheduling (CLTS) algorithm. The system scalability test proves that the TOGP has good horizontal scalability. In the comparative experiment, the processing capacity of the TOGP using the round robin is about 16% higher than that of Hadoop, which proves that the TOGP is available and efficient. A series of experiments prove that the CLTS scheduling algorithm can effectively adapt to the heterogeneous cluster environment and efficiently schedule tasks.

The electric energy system is undergoing a major change due to the increasing requirements of dynamic performance. In distribution grids, this evolution will necessitate expanded automation, which in turn will require enhanced connectivity solutions. Strongly evolving communications technologies and architectures, particularly mobile communications as well as cloud and edge computing, will provide new opportunities and alternatives for connectivity solutions. This paper contributes by identifying potential technical and industry architectures for the connectivity solutions required to manage distribution grids in the early 2030s. The study utilizes a senior expert panel and a Delphi survey. Industry architectures are modelled as value networks. The paper uses the Finnish distribution grids as a case example. Regarding technical architectures, the results reveal skepticism concerning those emerging 5G mobile network features that target industrial applications and about the need for extensive distributed computing in the proximity of consumers and prosumers. The most probable industry architectures are found to be those that enable the Distribution System Operators (DSOs) to maintain direct control of critical technical components, or that enable Communications Service Providers (CSPs) to handle the operations of both communications solutions and distributed computing. CSPs are seen as well positioned for this task due to their existing networking and computing infrastructure. However, this may also involve business risks for both DSOs and CSPs.

The distributed matrix multiplication problem with an unknown number of stragglers is considered, where the goal is to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across $N$ servers. There are up to $N - R$ stragglers but the exact number is not known a priori. Motivated by reducing the computation load of each server, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing task for each server is separated into several subtasks, constructed based on Entangled Polynomial codes by Yu et al. The final results can be obtained from either a larger number of servers with a smaller amount of computation completed per server or a smaller number of servers with a larger amount of computation completed per server. The required finite field size of the proposed solution is less than $2N$. Moreover, the optimal design parameters such as the partitioning of the input matrices are discussed. Our constructions can also be generalized to other settings such as batch distributed matrix multiplication and secure distributed matrix multiplication. [ABSTRACT FROM AUTHOR]

Most of our lives are conducted in the cyberspace. The human notion of privacy translates into a cyber notion of privacy on many functions that take place in the cyberspace. This article focuses on three such functions: how to privately retrieve information from cyberspace (privacy in information retrieval), how to privately leverage large-scale distributed/parallel processing (privacy in distributed computing), and how to learn/train machine learning models from private data spread across multiple users (privacy in distributed (federated) learning). The article motivates each privacy setting, describes the problem formulation, summarizes breakthrough results in the history of each problem, and gives recent results and discusses some of the major ideas that emerged in each field. In addition, the cross-cutting techniques and interconnections between the three topics are discussed along with a set of open problems and challenges. [ABSTRACT FROM AUTHOR]