Search

The paper aims at mitigating hot-spots during Offline Scheduling in IaaS (Infrastructure-as-a-Service) cloud systems. Unlike previous studies, the research focuses on identifying and resolving hot-spots not at servers, but at server racks. A two-phase algorithm for performing power-aware offline scheduling is proposed. The first phase aims at identifying and mitigating hot-spots at racks, while the second phase performs VM consolidation, i.e. minimization of the number of occupied servers while maintaining a feasible VM mapping and low migration costs. The proposed algorithm takes into account the dynamic nature of VM's resource consumption: it does not only resolve detected hot-spots, but also tries to avoid hot-spots in a reasonable future time period. The algorithm was tested with the data from a real IaaS cloud with different sets of algorithm's parameters. Experimental evaluation showed that the statistical estimates of the future VM's resource consumption provide the most reliable mapping, which is a result of minimization of the number of new hot-spot occurrences. • A server rack is a hot-spot if it exceeds the upper bound of power consumption. • Hot-spot identification, mitigation, and avoidance is crucial for IaaS systems. • An algorithm is proposed for rack hot-spot mitigation and consolidation of VMs. • Considering future CPU utilization values is associated with migrating more memory. • Ignoring future CPU utilization values leads to more new hot-spots happening shortly. [ABSTRACT FROM AUTHOR]

• The adaptive bulk search is a QUBO solver alternative to quantum annealing. • The cyclic-min algorithm is a SA-like algorithm without random number generation. • The bit permutated cyclic-min algorithm provides near-optimal solutions for QUBO. • Our scalable implementation attains linear improvement of the search rate. A wide range of combinatorial optimization problems can be reduced to the Ising model, and equivalently the quadratic unconstrained binary optimization (QUBO) problem. Thus, in recent years, researchers have proposed to solve QUBO on FPGAs, GPUs, and special-purpose processors. The adaptive bulk search (ABS) is a previously-proposed framework for solving QUBO in parallel on multiple GPUs. In the ABS, a CPU host performs a GA-based global search while GPUs asynchronously perform many local searches in parallel. An original ABS adopts a simple local search algorithm called a cyclic-min algorithm, which does not use pseudo random numbers. However, the lack of randomness may cause a potential drawback of restricted bit-flipping operations in a local search. To avoid this drawback, this paper proposes a cyclic-min algorithm with randomly-generated multiple bit permutations, which enables a more effective local search with random number generation in CPUs (not in GPUs). Furthermore, this paper introduces a scalable implementation of the ABS with MPI and OpenMP. Our experimental results on TSUBAME3.0 show that the solution quality improves and the throughput linearly increases as the number of GPUs increases; with 256 GPUs, it evaluates 20.1 × 10 12 solutions per second. [ABSTRACT FROM AUTHOR]

Resource provisioning plays a pivotal role in determining the right amount of infrastructure resource to run applications and reduce the monetary cost. A significant portion of production clusters is now dedicated to long-running applications (LRAs), which are typically in the form of microservices and executed in the order of hours or even months. It is therefore practically important to plan ahead the placement of LRAs in a shared cluster for the minimized number of compute nodes required by them. Existing works on LRA scheduling are often application-agnostic, without particularly addressing the constraining requirements imposed by LRAs, such as co-location affinity constraints and time-varying resource requirements. In this paper, we present an affinity-aware resource provisioning approach for deploying large-scale LRAs in a shared cluster subject to multiple constraints, with the objective of minimizing the number of compute nodes in use. We investigate a broad range of solution algorithms which fall into three main categories: Application-Centric, Node-Centric, and Multi-Node approaches, and tune them for typical large-scale real-world scenarios. Experimental studies driven by the Alibaba Tianchi dataset show that our algorithms can achieve competitive scheduling effectiveness and running time, as compared with the heuristics used by the latest work including Medea and Lra Sched. Best results are obtained by the Application-Centric algorithms, if the algorithm's running time is of primary concern, and by Multi-Node algorithms, if the solution quality is of primary concern. • Resource provisioning for long-running applications is studied in shared clusters. • Temporal resource requests and application-level affinity are considered. • Application-Centric algorithms win if the running time is of primary concern. • Node-Centric Algorithms offer a trade-off between solution quality and time. [ABSTRACT FROM AUTHOR]

One of the key objectives in many fields in machine learning is to discover causal relationships among a set of variables from observational data. In linear non-Gaussian acyclic models (LiNGAM), it can be shown that the true underlying causal structure can be identified uniquely from merely observational data. The DirectLiNGAM algorithm is a well-known solution to learn the true causal structure in a high dimensional setting. DirectLiNGAM algorithm executes in a sequence of iterations and it performs a set of comparisons between pairs of variables in each iteration. Unfortunately, the runtime of this algorithm grows significantly as the number of variables increases. In this paper, we propose a parallel algorithm, called ParaLiNGAM, to learn casual structures based on DirectLiNGAM algorithm. We propose a threshold mechanism that can reduce the number of comparisons remarkably compared with the sequential solution. Moreover, in order to further reduce runtime, we employ a messaging mechanism between workers. We also present an implementation of ParaLiNGAM on GPU, considering hardware constraints. Experimental results on synthetic and real data show that our proposed solution outperforms DirectLiNGAM by a factor up to 4788X, and by a median of 2344X. • A scalable algorithm for learning causal structures in linear non-Gaussian models. • Significant speedup by selecting the necessary computations judiciously. • Speedup ratio of up to 4788 on GPUs in real-world and synthetic datasets. [ABSTRACT FROM AUTHOR]

In edge computing, application components can be placed over a range of computational devices from cloud data centers to nodes at the network edge. Application placement can have significant impact on important metrics like latency and resource utilization. Thus, application placement is an important optimization problem. In edge computing, the characteristics of both the infrastructure and the application may change over time, which may require the dynamic re-optimization of the application placement. Most algorithms suggested so far for the dynamic re-optimization of edge application placement are centralized, i.e., they rely on one entity collecting information from the whole infrastructure and making decisions centrally. However, centralized approaches suffer from limited scalability and are vulnerable to failures. In this paper, we present a decentralized approach for the dynamic re-optimization of edge application placement. We adopt an algorithm of Malek et al. for distributed systems and modify it to make it applicable to edge computing. In this approach, each node makes decisions autonomously, using auctions for coordination. Our empirical results demonstrate that the proposed algorithm is very effective in optimizing edge application placement. In an edge system with 637 edge nodes and 563 end devices, our algorithm achieves 54% higher reduction of application latency than a previous decentralized algorithm. • Optimized placement of application components on cloud and edge devices. • Decentralized optimization algorithm using local knowledge and local modifications. • Auctions and distributed locking for synchronization. • Minimization of application latency. [ABSTRACT FROM AUTHOR]

In this paper, we describe the first parallel Branch-and-Bound (B&B) algorithm with a history-based domination technique. Although history-based domination substantially speeds up a B&B search, it makes parallelization much more challenging. Our algorithm is the first parallel exact algorithm for the Sequential Ordering Problem using a pure B&B approach. To effectively explore the solution space, we have developed three novel parallelization techniques: thread restart, parallel history domination, and history-table memory management. The proposed algorithm was experimentally evaluated using the SOPLIB and TSPLIB benchmarks on multi-core processors. Using 32 threads with a time limit of one hour, the algorithm gives geometric-mean speedups of 72x and 20x on the medium-difficulty SOPLIB and TSPLIB instances, respectively. On the hard instances, it solves 12 instances that the sequential algorithm does not solve, with geometric-mean speedups of 16x on SOPLIB and 32x on TSPLIB. Super-linear speedups up to 366x are seen on 16 instances. • We propose the first parallel B&B algorithm that involves a history-based domination technique. • The proposed algorithm includes three novel parallelization techniques: thread restart, parallel history-based domination, and history-table memory management. • The proposed algorithm is the first parallel B&B algorithm for the Sequential Ordering Problem, which is an NP-hard sequencing problem with precedence constraints. • We present a thorough experimental evaluation of the proposed parallel algorithm on SOPLIB and TSPLIB. The results show that super-linear speedup is not an anomaly; it can be achieved on many instances. We report a speedup ratio as high as 285 on a 32-core processor. [ABSTRACT FROM AUTHOR]

• Formulate a non-cooperative game with both UEs and MECs as players. • Prove the existence of and convergence to a Nash equilibrium. • Develop a set of algorithms to find the Nash equilibrium. • Demonstrate numerical examples of non-cooperative games with and without MECs' participation. In a newly emerged fog computing environment, various user equipments (UE) enhance their computing power and extend their battery lifetime by computation offloading to mobile edge cloud (MEC) servers. Such an environment is distributed and competitive in nature. In this paper, we take a game theoretical approach to computation offloading optimization in a fog computing environment. Such an approach captures and characterizes the nature of a competitive environment. The main contributions of the paper can be summarized as follows. First, we formulate a non-cooperative game with both UEs and MECs as players. Each UE attempts to minimize the execution time of its tasks with an energy constraint. Each MEC attempts to minimize the product of its power consumption for computation and execution time for allocated tasks. Second, we develop a heuristic algorithm for a UE to determine its "heuristically" best response to the current situation, an algorithm for an MEC to determine its best response to the current situation, and an iterative algorithm to find the Nash equilibrium. Third, we prove that our iterative algorithm converges to a Nash equilibrium. We demonstrate numerical examples of our non-cooperative games with and without MECs' participation. We observe that our iterative algorithm always quickly converges to a Nash equilibrium. The uniqueness of our non-cooperative games is that the strategy set of a player can be discrete and the payoff function of a player can be obtained by a heuristic algorithm for combinatorial optimization. To the best of the author's knowledge, there has been no such investigation of non-cooperative games based on combinatorial optimization for computation offloading optimization in a fog computing environment. [ABSTRACT FROM AUTHOR]

The paper presents a new method of optimization by the Layered Algorithm (LA). The proposed algorithm reduces the initial area to the sub-area containing the optimum. The proposed technique is based on the classification of the optimized function values (data sampled by sensors). The classification method uses a two-dimensional three-state Cellular Automata (CA). The CA classifies all area points ascribed to the CA cells based on their values. Specification of the categorization layers to the data gives a possibility to identify the different levels areas. Consequently, after analysis, a sub-area containing the optimum can be designated. In this paper, the proposed algorithm is applied to find the location of the airborne contaminant source by analyzing the concentration of released substances reported by mobile sensors distributed over the domain of interest. The Gaussian dispersion model simulation of the contaminant dispersion in the urbanized area is applied to generate the data used to verify the efficiency of the proposed Layered Algorithm. The LA successfully estimates the sub-area of the considered domain where the contamination source is located, taking to account data from sensors solely. • Optimization method reducing the initial area to the sub-area containing the optimum. • Verification of the Layered Algorithm (LA) with Selected Benchmark Functions. • Analysis of the LA efficiency to localize the airborne contaminant source. • LA results assessment by the measures: classification and accuracy error, relevance. [ABSTRACT FROM AUTHOR]

• A network flow model of the VLSI processor array is constructed under row and column rerouting. • A new strategy for selecting the bottleneck row in the logic array using the minimum cutting technique is proposed. • The proposed schemes significantly reduce the interconnect redundancy of the logical subarray. The reconfiguration algorithms have been extensively investigated to ensure the reliability and stability for the processor arrays with faults. It is important to reduce the power consumption, capacitance and communication costs in the processors by reducing the interconnection length of the VLSI array. This paper discusses the reconfiguration problem of the high-performance VLSI processor array under the row and column rerouting constraints. A novel method, making use the idea of network flow, is proposed in this paper. Firstly, a network flow model of the VLSI processor array is constructed, such that the high-performance VLSI target array can be obtained by utilizing the minimal cost flow algorithm. Secondly, we propose a new strategy for bottleneck row selection in the logical array using the minimum cut technique, which can find a more suitable bottleneck row. Finally, we conducted reliable experiments to clearly reveal the efficiency of the new rerouting scheme and algorithm in reducing the number of long interconnects. The experimental results show that, for a host array with size of 256×256, the number of long interconnects in the subarray can be reduced by up to 79.22% and 55.88% without performance penalty for random faults with density of 1% and 25% respectively, when compared with state-of-the-art. In addition, the proposed scheme improves existing algorithm in terms of subarray size. On a 256×256 host array with 25% faulty density, the average improvement in subarray size is up to 3.77% compared with state-of-the-art. [ABSTRACT FROM AUTHOR]

Structural plasticity of the brain describes the creation of new and the deletion of old synapses over time. Rinke et al. (JPDC 2018) introduced a scalable algorithm that simulates structural plasticity for up to one billion neurons on current hardware using a variant of the Barnes–Hut algorithm. They demonstrate good scalability and prove a runtime complexity of O (n log 2 ⁡ n). In this comment paper, we show that with careful consideration of the algorithm and a rigorous proof, the theoretical runtime can even be classified as O (n log ⁡ n). • Improved serial runtime bound for the adapted Barnes–Hut algorithm to Θ(n*log(n)). • Improved the parallel runtime bound to Θ(n/p*log(n)+p). • Mathematical justification that the given runtime bound is sharp. [ABSTRACT FROM AUTHOR]

Path planning is an NP-hard problem that is aimed to satisfy multi-constraint optimization requirements. In autonomous robotics applications, path planning together with collision avoidance presents a challenging task. It necessitates the generation of possible search directions from a designated point to a fixed varying destination location satisfying spatial constraints. This paper presents a framework for the design of an intelligent multi-objective robotic path planning algorithm. The algorithm relies on the generation of way-points by hybridizing two meta-heuristics techniques, namely Grey Wolf Algorithm (GWO) and Particle Swarm Optimization (PSO). A frequency-based modification in GWO search operators is introduced to fasten the search process. An improvised search strategy is employed for collision detection and avoidance, which converts non-desired points into the desired point. Sensors are deployed around the robot vicinity for search optimization. Mutation operators are then introduced to improve path length by smoothing out the trajectory. The proposed algorithm's effectivity is then validated through extensive simulations, in which different condition environments are simulated. To validate the effectiveness of the proposed methodology, the results are compared with contemporary algorithms namely Minimum Angle Artificial Bee Colony (MAABC) algorithms, Hybrid Cuckoo Search-Bat Algorithm (BA-CSA), Bacterial Bolony (BC) and Genetic Algorithm (GA) algorithms. The results conclusively demonstrated that the proposed algorithm ensures effective performance in path smoothness and safety under a wide range of conditions. • A novel intelligent multi-objective framework for robotic path planning algorithm. • A hybridizing two meta-heuristics techniques to solve the path planning. • An improvised search strategy is employed for collision detection and avoidance. • The proposed algorithm's effectively validated through extensive simulations. [ABSTRACT FROM AUTHOR]

Communication overhead is the key challenge for distributed training. Gradient compression is a widely used approach to reduce communication traffic. When combined with a parallel communication mechanism method like pipeline, gradient compression technique can greatly alleviate the impact of communication overhead. However, there exist two problems of gradient compression technique to be solved. Firstly, gradient compression brings in extra computation cost, which will delay the next training iteration. Secondly, gradient compression usually leads to a decrease in convergence accuracy. In this paper, we combine parallel mechanism with gradient quantization and periodic full-gradient compensation, and propose a new distributed optimization method named CP-SGD, which can hide the overhead of gradient compression, overlap part of the communication and obtain high convergence accuracy. The local update operation in CP-SGD allows the next iteration to be launched quickly without waiting for the completion of gradient compression and the current communication process. Besides, the accuracy loss caused by gradient compression is solved by k-step correction method introduced in CP-SGD, which provides a gradient correction every k iterations. We prove that CP-SGD has a convergence guarantee and it achieves at least O (1 K + 1 K) convergence rate, where K is the number of iterations. We conduct extensive experiments on MXNet to verify the convergence properties and scaling performance of CP-SGD. Experimental results on a 32-GPU cluster show that convergence accuracy of CP-SGD is close to or even slightly better than that of S-SGD, and its end-to-end time is 30% less than 2-bit gradient compression under a 56Gbps bandwidth environment. In addition, we analyze the performance of CP-SGD when training on 8, 16 and 32 GPUs. It is found that CP-SGD is suitable for most compression-supported update algorithms, and its scalability is approximately linear. • CP-SGD: Distributed Stochastic Gradient Descent with Compression and Periodic Compensation. • CP-SGD help distributed deep learning train with high-accuracy and friendly-communication simultaneously. • Combining the advantages of parallel mechanism and gradient compression. • K-step correction technique makes CP-SGD achieve codesign optimizations and improve compression-based methods greatly. • CP-SGD suits most compression-supported update algorithms and gradient compression strategies. [ABSTRACT FROM AUTHOR]

• A parallel scalable DBSCAN algorithm which outperforms other implementations. • Optimizations for data partitioning, spatial indexing, and cluster merging. • Exploiting hybrid parallelization to take advantage of modern HPC architectures. • Demonstrating accuracy, performance and scalability of our algorithm. Dbscan is a density-based clustering algorithm which is well known for its ability to discover clusters of arbitrary shape as well as to distinguish noise. As it is computationally expensive for large datasets, research studies on the parallelization of Dbscan have been received a considerable amount of attention. In this paper we present an exact, efficient and scalable parallel Dbscan algorithm which we call Hy-Dbscan. It employs three major techniques to enable scalable data clustering on distributed-memory computers i) a modified kd-tree for domain decomposition, ii) a spatial indexing approach based on grid and inference, and iii) a cluster merging scheme based on distributed Rem's Union-Find algorithm. Moreover, Hy-Dbscan exploits process level and thread level parallelization. In experiments, we have demonstrated performance and scalability using two scientific datasets on up to 2048 cores of a distributed-memory computer. Through extensive evaluation, we show that Hy-Dbscan significantly outperforms previous state-of-the-art Dbscan implementations. [ABSTRACT FROM AUTHOR]

This paper examines a novel parallel computation model called bulk synchronous farm (BSF) that focuses on estimating the scalability of compute-intensive iterative algorithms aimed at cluster computing systems. The main advantage of the proposed model is that it allows to estimate the scalability of a parallel algorithm before its implementation. Another important feature of the BSF model is the representation of problem data in the form of lists that greatly simplifies the logic of building applications. In the BSF model, a computer is a set of processor nodes connected by a network and organized according to the master/slave paradigm. A cost metric of the BSF model is presented. This cost metric requires the algorithm to be represented in the form of operations on lists. This allows us to derive an equation that predicts the scalability boundary of a parallel program: the maximum number of processor nodes after which the speedup begins to decrease. The paper includes examples of applying the BSF model to designing and analyzing parallel numerical algorithms. The large-scale computational experiments conducted on a cluster computing system confirm the adequacy of the analytical estimations obtained using the BSF model. • Scalability is important property of parallel algorithm. • The main measure for evaluating scalability is speedup. • Algorithm is scalable if speedup increases linearly with number of processors. • Scalability boundary is number of processors at which speedup peak is reached. • Parallel computation model can predict scalability boundary of parallel algorithm. [ABSTRACT FROM AUTHOR]

Network coding and topology control techniques have been widely used to increase throughput and improve the lifetime of Wireless Sensor Networks (WSNs). This paper considers the simultaneous utilization of these techniques in a WSN and proposes convex non-linear programming. Since solving the problem for a large-scale and dynamic WSN is impractical and almost impossible, Lagrangian, sub-gradient and the decomposition methods are employed to provide a decentralized algorithm. In the proposed algorithm, a node makes the computations by acquiring local knowledge and information from its neighbors. This paper provides a mathematical language to build an analytic foundation for the design of a modularized and decentralized algorithm that provides transmission ranges and routes for a WSN. The simulation results show that increasing the number of sources, sinks, sensors, and traffic load leads to improving the lifetime which is acquired by the proposed algorithm. [ABSTRACT FROM AUTHOR]

IoT environments are continuously changing. Changes may come from the service, connectivity, or physical layers of the IoT architecture. Therefore, to function appropriately, the system needs to dynamically adapt to its environment. In previous work, we posited eight challenges to foster adaptation through all architecture layers of IoT systems. In this paper, we address the challenges to manage the inclusion of new devices and devices' transient connection , by means of dynamic adaptations incorporated into our proposed software architecture for adaptive IoT systems. To manage dynamic adaptations, we extend the reference IoT architecture with our specialized components. In particular, we use (1) ontologies and instances to represent the domain knowledge; (2) a matching algorithm to pair services and IoT devices, taking into account their functional requirements, quality attributes and sensors properties; and (3) a match update algorithm used whenever sensors become (un)available. We evaluate the effectiveness of our solution with respect to the accuracy of matching services and IoT devices, and the response to environment changes. • This paper presents a new adaptive architecture for IoT Systems. • Ontology matching algorithm-based architecture to manage transient connections. • Functional, non-functional, and QoS matching algorithm between IoT components. • Matching algorithm with better precision and recall compared with the gold-standard. • Architecture deployed in a real case study for a SUDS system in the city of Bogotá. [ABSTRACT FROM AUTHOR]

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and secure message distribution. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Kao et al. (2019) [18] proposed an algorithm to construct independent spanning trees in bubble-sort networks. The algorithm is executed in a recursive function and thus is hard to parallelize. In this paper, we focus on the problem of constructing ISTs in bubble-sort networks B n and present a non-recursive algorithm. Our approach can be fully parallelized, i.e., every vertex can determine its parent in each spanning tree in constant time. This solves the open problem from the paper by Kao et al. Furthermore, we show that the total time complexity O (n ⋅ n !) of our algorithm is asymptotically optimal, where n is the dimension of B n and n ! is the number of vertices of the network. • We present an algorithm for constructing multiple independent spanning trees in bubble-sort networks. • Our approach can be fully parallelized, thus solving an open problem from Kao et al. (2019). • We show that the total time complexity of our algorithm is asymptotically optimal. [ABSTRACT FROM AUTHOR]

The vigorous development and the increasing popularity of cloud computing highlight the necessity of reducing data center energy consumption and the environmental impact of carbon dioxide emissions. For geographically distributed data centers, cloud servers are connected to the conventional power grid and in addition they are supported by an attached renewable energy source. Since the carbon footprint rate of energy consumption has dynamic differences in space, reducing energy consumption does not mean decrease carbon emission, which indicates that energy consumption and carbon footprint need to be synergistically optimized. In this paper, an energy and carbon-aware algorithm for virtual machine placement is proposed. The goal is to obtain a virtual machine allocation scheme that aims to achieve the trade-off between energy consumption and carbon emissions by improving renewable energy utilization. The experimental results show that the proposed approach is more energy-efficient and greener, which can also maximize the renewable energy utilization with 73.11% while ensuring the SLA violation with 0.2% in comparison to the baseline algorithms. • Propose a novel energy-aware VM placement approach in cloud data centers. • Introduce renewable energy for managing energy consumption and carbon footprint. • Design renewable energy generation prediction method based on EEMD and TCN. • Demonstrate the superiority of the proposed algorithm with five baseline algorithms. [ABSTRACT FROM AUTHOR]

The performance of collective communication operations determines the overall performance of MPI applications. Different algorithms have been developed and implemented for each MPI collective operation, but none proved superior in all situations. Therefore, MPI implementations have to solve the problem of selecting the optimal algorithm for the collective operation depending on the platform, the number of processes involved, the message size(s), etc. The current solution method is purely empirical. Recently, an alternative solution method using analytical performance models of collective algorithms has been proposed and proved both accurate and efficient for one-process-per-CPU configurations. The method derives the analytical performance models of algorithms from their code implementation rather than from high-level mathematical definitions, and estimates the parameters of the models separately for each algorithm. The method is network and topology oblivious and uses the Hockney model for point-to-point communications. In this paper, we extend that selection method to the case of clusters of multi-core processors, where each core of the platform runs a process of the MPI application. We present the proposed approach using Open MPI broadcast algorithms, and experimentally validate it on three different clusters of multi-core processors, Grisou, Gros and MareNostrum4. • A novel model-based method for runtime selection of optimal collective algorithms. • Application of the proposed method to the Open MPI broadcast algorithms. • Experimental validation of the method on two modern multi-core clusters. [ABSTRACT FROM AUTHOR]

• Our algorithm is more efficient, has less communication overhead, and has greater throughput than the original PBFT algorithm. • We propose a Vehicle - Service Provider - Roadside Unit architecture to ensure the orderliness and safety of vehicles. • We propose an identity authentication scheme based on blockchain. • Experimental results demonstrate that our solution is better than PBFT, G-PBFT and CPBFT. As an application of Internet of Things (IoT) technology, the Internet of Vehicles (IoV) faces two main security issues: (1) the central server of the IoV may not be powerful enough to support the centralized authentication of the rapidly increasing connected vehicles, (2) the IoV itself may not be robust enough to single-node attacks. To address these issues, in this paper, we propose SG-PBFT (Score Grouping-PBFT), a secure and efficient distributed consensus algorithm for blockchain applications in the IoV. The distributed structure can reduce the pressure on the central server and decrease the risk of single-node attacks. The SG-PBFT consensus algorithm improves the traditional practical Byzantine fault tolerance (PBFT) consensus algorithm by optimizing the PBFT consensus process and using a score grouping mechanism to achieve a higher consensus efficiency. The experimental results show that the method can greatly improve the consistency efficiency and effectively prevent single-node attacks. Specifically, when the number of consensus nodes reaches 1000, the consensus time of our algorithm is only about 27% of what is required for the state-of-the-art PBFT consensus algorithm. Our proposed SG-PBFT algorithm is versatile and can be used in other application scenarios which require high consensus efficiency. [ABSTRACT FROM AUTHOR]

Multi/Many-core systems based on the traditional electrical network-on-chip are confronted with the limited bandwidth, high latency, and reliability challenges. The emerging optical solution of silicon photonics has promised to improve the design parameters of electrical interconnections for future multiprocessor system on chips. Although the optical network-on-chip has advantages in terms of reliability compared to the electrical ones, important phenomena such as crosstalk noise, process variation, and temperature fluctuations must be carefully considered. These physical challenges have substantial adverse effects on the correct functionality of on-chip optical devices such as microring resonator and the optical waveguide. Malfunction of these elements may cause the injection of faults that should be tolerated by the reliable system. In this paper, we have assessed the effect of the fault-tolerant design of optical routers on the reliability parameters through application mapping. We propose a fault-tolerant algorithm to modify optical routers to improve the reliability parameter. The vulnerability analysis of the proposed algorithm shows that besides obtaining the fault-tolerant capability in optical routers, only about 9.63% and 19.29% of SNR decrease for real-world applications and seven traditional optical routers are achieved in the case of a single fault and two faults injections, respectively. • In the first step, we explain the primitives of optical on-chip data transmission and discuss on its reliability challenges and also the paper's motivation. • A general framework to construct a fault-tolerant optical router. • Evaluation the reliability parameters of various fault-tolerant optical routers. • Optimized application mapping for fair comparison in different optical routers. • Vulnerability analysis through fault injection for the proposed fault-tolerant schema. [ABSTRACT FROM AUTHOR]

It has been shown that any nonblocking algorithm for work-stealing in the standard asynchronous shared memory model of computation must use expensive Read-After-Write synchronization patterns or atomic Read-Modify-Write instructions. Algorithms for relaxations of work-stealing have been proposed, which only partially avoid this impossibility result. In restricted models of computation, work-stealing algorithms have been designed that avoid Read-After-Write patterns and atomic Read-Modify-Write instructions. This paper considers work-stealing with multiplicity , a relaxation in which every task is taken by at least one process, and any process can take any task at most once. We study two variants of the relaxation, for each variant designing a Read / Write wait-free algorithm in the standard asynchronous shared memory model. The two algorithms are devoid of Read-After-Write synchronization patterns in all their operations, and additionally, the algorithm for the second variant has constant step complexity and is fence-free. Namely, no specific ordering among the algorithm's instructions is required beyond what is implied by data dependence. To our knowledge, these are the first algorithms for relaxations of work-stealing possessing all these properties. The algorithms are also solutions to relaxed versions of single-enqueuer multi-dequeuer queues. The theoretical results are complemented with an experimental evaluation showing that the benefits of relaxed work-stealing vary depending on the application, concretely on the complexity of the work associated with each task. • We present two asynchronous work-stealing algorithms with relaxation, work-stealing with multiplicity and weak-multiplicity. • In the first one, tasks are taken by at least one operation and if taken by several operations, they must be pairwise concurrent. • In the second one, Take/Steal operations extracting the same task may not be concurrent, however, each process extracts tasks at most once. • The algorithms are wait-free, read/write, and devoid of read-after-write synchronization patterns. • The proposed algorithms outperform standard work-stealing algorithms and exhibit similar or better performance than known relaxed algorithms in some practical settings. [ABSTRACT FROM AUTHOR]

Atomic Broadcast is an essential broadcast primitive as it ensures the consistency of distributed replicas. However, it is notoriously non-scalable. In this work, we introduce the Leaderless Hierarchical Atomic Broadcast (LHABcast) algorithm, which has two properties to improve scalability. First, it is a fully decentralized algorithm that does not rely on a sequencer/leader, which is often a significant bottleneck. Processes running LHABcast send messages with local sequence numbers and order messages received from other processes using timestamps inspired on Lamport's logical clocks. A process that receives the required set of timestamps can make a decision about the overall sequence of message delivery. Second, the algorithm is hierarchical: processes are organized on a vCube logical overlay network, which has several logarithmic properties and allows the construction of autonomous spanning trees. vCube also works as a failure detector, assuming crash faults and an asynchronous system model. In this paper, LHABcast is described, specified, and proven to be correct. Both simulation and experimental results are presented. A comparison with an all-to-all strategy shows that the number of messages sent by LHABcast is significantly lower in both fault-free and faulty scenarios. An implementation of LHABcast in Akka.io achieved up to 3.9 times higher throughput in fault-free scenarios than an implementation of the Raft-based Apache Ratis. • LHABcast is a fully decentralized leaderless algorithm broadcast algorithm. • LHABcast organizes processes on a vCube, which has several logarithmic properties. • LHABcast uses autonomic spanning trees rooted at the sender for message dissemination. • LHABcast is described with examples, and multiple properties are proved. • LHABcast was evaluated both with a Neko simulation and using the Java Akka framework. [ABSTRACT FROM AUTHOR]

Synchronous SGD with data parallelism, the most popular parallelization strategy for CNN training, suffers from the expensive communication cost of averaging gradients among all workers. The iterative parameter updates of SGD cause frequent communications and it becomes the performance bottleneck. In this paper, we propose a lazy parameter update algorithm that adaptively adjusts the parameter update frequency to address the expensive communication cost issue. Our algorithm accumulates the gradients if the difference of the accumulated gradients and the latest gradients is sufficiently small. The less frequent parameter updates reduce the per-iteration communication cost while maintaining the model accuracy. Our experimental results demonstrate that the lazy update method remarkably improves the scalability while maintaining the model accuracy. For ResNet50 training on ImageNet, the proposed algorithm achieves a significantly higher speedup (739.6 on 2048 Cori KNL nodes) as compared to the vanilla synchronous SGD (276.6) while the model accuracy is almost not affected (<0.2% difference). • Adaptive parameter update frequency control for scalable parallel deep learning. • Allowing gradient accumulation considering the direction of the gradients. • Reducing per-iteration communication cost at the input side model layers. • Overlapping gradient communications with backpropagation computations. [ABSTRACT FROM AUTHOR]

• Limited power of randomization in dealing with adaptive adversaries. • Derandomizing algorithms via simulation. • Simulating a dynamic network on top of another dynamic network. This paper investigates the power of randomization in general distributed algorithms in dynamic networks where the network's topology may evolve over time, as determined by some adaptive adversary. In such a context, randomization may help algorithms to better deal with i) "bad" inputs to the algorithm, and ii) evolving topologies generated by "bad" adaptive adversaries. We prove that randomness offers limited power to better deal with "bad" adaptive adversary. We define a simple notion of prophetic adversary for determining the evolving topologies. Such an adversary accurately predicts all randomness in the algorithm beforehand, and hence the randomness will be useless against "bad" prophetic adversaries. Given a randomized algorithm P whose time complexity satisfies some mild conditions, we prove that P can always be converted to a new algorithm Q with comparable time complexity, even when Q runs against prophetic adversaries. This implies that the benefit of P using randomness for dealing with the adaptive adversaries is limited. [ABSTRACT FROM AUTHOR]

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]

• Propose the aligned storage formats ACSR and AELL. • Put forward a parallel SpMV algorithm based on ACSR and AELL formats. • Theoretically analyze the performance of SpMV on ARM processors. • Evaluate the performance of our optimization on Kunpeng 920 processors. Sparse matrix-vector multiplication (SpMV) has always been a hot topic of research for scientific computing and big data processing, but the sparsity and discontinuity of the nonzero elements in a sparse matrix lead to the memory bottleneck of SpMV. In this paper, we propose aligned CSR (ACSR) and aligned ELL (AELL) formats and a parallel SpMV algorithm to utilize NEON SIMD registers on ARM processors. We analyze the impact of SIMD instruction latency, cache access, and cache misses on SpMV with different formats. In the experiments, our SpMV algorithm based on ACSR achieves 1.18x and 1.56x speedup over SpMV based on CSR and SpMV in PETSc, respectively, and AELL achieves 1.21x speedup over ELL. The deviations between the theoretical results and experimental results in the instruction latency and cache access are 10.26% and 10.51% in ACSR and 5.68% and 2.91% in AELL, respectively. [ABSTRACT FROM AUTHOR]

Failure detectors (FD)s are celebrated for their modularity in solving distributed problems. Algorithms are constructed using FD building blocks. Synchrony assumptions to implement FDs are studied separately and are typically expressed as eventual guarantees that need to hold, after some point in time, forever and deterministically. But in practice, they may hold only probabilistically and temporarily. This paper studies FDs in a realistic system N , where asynchrony is inflicted by probabilistic synchronous communication. We first address a problem with ⋄ S , the weakest FD to solve consensus: an implementation of "consensus with probability 1" is possible in N without randomness in the algorithm, while an implementation of " ⋄ S with probability 1" is impossible in N. We introduce ⋄ S ⁎ , a new FD with probabilistic and temporal accuracy. We prove that ⋄ S ⁎ (i) is implementable in N and (ii) can replace ⋄ S , in several existing deterministic consensus algorithms that use ⋄ S , to yield an algorithm that solves "consensus with probability 1". We extend our results to other FD classes, e.g., ⋄ P , and to a larger set of problems (beyond consensus), which we call decisive problems. • We propose a way to preserve the usefulness of failure detectors (FD)s as software building blocks in probabilistically synchronous systems as (N). • We define <>S*, a probabilistic FD with accuracy ensured for arbitrarily long finite periods and that can be implemented in systems as N. • We present an optimal <>S* algorithm, which achieves in the best case the lowest communication overhead (C-1) compared to all known <>S algorithms. • We extend our FD definitions for other FD classes and other distributed computing problems besides consensus, which we call decisive problems. • We encapsulate the randomization of probabilistic links in the very abstraction of FD, without affecting deterministic algorithms built on top. [ABSTRACT FROM AUTHOR]

• The placement of data and the scheduling of request are studied in edge caching. • Network unreliability and limited storage and bandwidth resources are considered. • Two algorithms with different computation complexity and cache efficiency are developed. • The experiments are conducted to evaluate the performance of proposed caching strategies. Edge caching is a prevailing media delivery technology where data is hosted at the edge nodes with computing and storage capability in close proximity to users, in order to expand the backhaul network capacity and enhance users' quality of experience (QoE). The existing work in this area often neglects the fact that large-scale distributed cache networks are not particularly reliable and many edge nodes are prone to failure. In this paper we investigate and develop a novel, cooperative caching mechanism for content placement and request routing. We aim to minimize the content access delay and achieve the optimization in polynomial time, taking into account failures in an unreliable network environment with limited edge storage and bandwidth. We introduce two optimization algorithms: 1) a primal-dual algorithm that is based on the Lagrangian dual decomposition and subgradient method, and 2) a greedy-based approximation algorithm with a proven approximation ratio. Numerical results show that the proposed algorithms outperform other comparative approaches in synthetic and real network environments, and the approximation algorithm is particularly suitable for networking scenarios with sparse node connectivity and resources in short supply. [ABSTRACT FROM AUTHOR]

• The Sigmoid algorithm applies the well-known sigmoid function to load balancing. • The algorithm uses all the resources of a system to their fullest requiring no effort. • It adapts to different hardware configurations and application behaviours. • Sigmoid successfully scales to adapt to the systems of the future. A challenge that heterogeneous system programmers face is leveraging the performance of all the devices that integrate the system. This paper presents Sigmoid, a new load balancing algorithm that efficiently co-executes a single OpenCL data-parallel kernel on all the devices of heterogeneous systems. Sigmoid splits the workload proportionally to the capabilities of the devices, drastically reducing response time and energy consumption. It is designed around several features; it is dynamic, adaptive, guided and effortless, as it does not require the user to give any parameter, adapting to the behaviour of each kernel at runtime. To evaluate Sigmoid's performance, it has been implemented in Maat, a system abstraction library. Experimental results with different kernel types show that Sigmoid exhibits excellent performance, reaching a utilization of 90%, together with energy savings up to 20%, always reducing programming effort compared to OpenCL, and facilitating the portability to other heterogeneous machines. [ABSTRACT FROM AUTHOR]

Mobile devices (MDs) and applications are receiving extensive popularity and attracting significant attention. Mobile applications, especially for artificial intelligence (AI) applications, require powerful computation-intensive resources. Hence, running all the AI applications on a single MD introduces high energy consumption and application delay, as it has limited battery capacity and computation resources. Fortunately, the emerging edge-cloud computing (ECC) architecture pushes the computation resource to both the network edge and remote cloud to cope with challenging AI applications. Although the advantage of ECC greatly benefits various mobile applications, data security remains an important open issue in this scenario, which has not been well studied. This paper focuses on the profit maximization (PM) problem for security-aware task offloading in an ECC environment, i.e., considering the tasks from MDs with different service demands, edge nodes should decide them to be processed on the edge node or the remote cloud with a security guarantee. Specifically, we first construct the security model to measure the time overhead for each task under various scenarios. We then formulate the PM problem by jointly considering the security demand and deadline constraints of tasks. Finally, we propose a genetic algorithm-based PM (GA-PM) algorithm, the coding strategy of which considers the task execution location and execution order. Moreover, the crossover and mutation operations are implemented based on the coding strategy. Extensive simulation experiments with various parameters varying demonstrate that our GA-PM can achieve better performance than all the comparison algorithms. • The security model is built to measure the execution time of tasks under different parameters. • A genetic algorithm (GA)-based PM algorithm is proposed to implement task offloading and obtain optimal profit. • A coding strategy is devised by considering the tasks execution location and execution order. • Extensive simulation results demonstrate that GA-PM algorithm achieves the optimal profit. [ABSTRACT FROM AUTHOR]

End-to-end integrity verification is used to avoid silent data corruption in file transfers by comparing the checksum of files at source and destination end points. However, it increases transfer times significantly as checksum computation requires reading files back from the storage and running compute-intensive hash computation. In this paper, we propose Fast Integrity VERification (FIVER) algorithm which alleviates the overhead of end-to-end integrity verification by overlapping checksum computation with transfer operation and enabling I/O sharing between the two. The results obtained from various network and dataset settings show that FIVER is able to bring down the cost of end-to-end integrity verification from up to 120% by the state-of-the-art solutions to below 15%. Moreover, existing implementations of end-to-end integrity verification are vulnerable to permanent data loss in the case of an unexpected power outage due to completing the integrity verification process while data is still on memory. FIVER addresses this issue by enforcing dirty data on memory to be flushed to disk before finishing integrity verification such that power loss during any phase of a transfer would cause integrity verification to fail and transfer application to retransfer lost data. • File transfers are vulnerable to data corruption and loss. • End-to-end integrity verification is important and can be implemented with minimal cost. • Write-back caching poses data permanent data risk for file transfers despite using end-to-end integrity verification. [ABSTRACT FROM AUTHOR]

Linear algebra operations have been widely used in big data analytics and scientific computations. Many works have been done on optimizing linear algebra operations on GPUs with regular-shaped input. However, few works focus on fully utilizing GPU resources when the input is not regular-shaped. Current optimizations do not consider fully utilizing the memory bandwidth and computing power; therefore, they can only achieve sub-optimal performance. In this paper, we propose two efficient algorithms – TSM2R and TSM2L – for two classes of tall-and-skinny matrix–matrix multiplications on GPUs. Both of them focus on optimizing linear algebra operation with at least one of the input matrices tall-and-skinny. Specifically, TSM2R is designed for a large regular-shaped matrix multiplying a tall-and-skinny matrix, while TSM2L is designed for a tall-and-skinny matrix multiplying a small regular-shaped matrix. We implement our proposed algorithms and test on several modern NVIDIA GPU micro-architectures. Experiments show that, compared to the current state-of-the-art works, (1) TSM2R speeds up the computation by 1.6x on average and improves the memory bandwidth utilization and computing power utilization by 18.1% and 20.5% on average, respectively, when the regular-shaped matrix size is relatively large or medium; and (2) TSM2L speeds up the computation by 1.9x on average and improves the memory bandwidth utilization by up to 9.3% on average when the regular-shaped matrix size is relatively small. • Few works focus on optimizing GEMM on GPUs for the irregular-shaped input. • Current optimizations do not fully utilize the memory bandwidth and computing power. • We propose two efficient algorithms for two classes of tall-and-skinny GEMM on GPUs. • Our optimizations speedup GEMM by 1.1x ∼ 3.5x for various tall-and-skinny inputs. [ABSTRACT FROM AUTHOR]

Hyperspectral image registration is a relevant task for real-time applications such as environmental disaster management or search and rescue scenarios. The HYFMGPU algorithm was proposed as a single-GPU high-performance solution, but the need for a distributed version has arisen due to the continuous evolution of sensors that generate images with finer spatial and spectral resolutions. In a previous work, we simplified the programming of the multi-device parts of an initial MPI+CUDA multi-GPU implementation of HYFMGPU by means of Hitmap, a library to ease the programming of parallel applications based on distributed arrays. The performance of that Hitmap version was assessed in a homogeneous GPU cluster. In this paper, we extend this implementation by means of new functionalities added to the latest version of Hitmap in order to support arbitrary load distributions for multi-node heterogeneous GPU clusters. Three different load balancing layouts are tested, which prove that selecting a proper layout affects the performance of the code and how this performance is correlated with the use of the GPUs available in the cluster. • Multi-GPU implementation of the HYFMGPU hyperspectral image registration algorithm. • New load balancing to adapt its performance to multi-GPU clusters capabilities. • Includes evaluation of proper load balancing vs distributed version performance. • Includes comparison of three different data layouts. • The bigger the inputs, the larger the performance impact of load balancing layout. [ABSTRACT FROM AUTHOR]

An increasing amount of malicious code causes harm on the internet by threatening user privacy as one of the primary sources of network security vulnerabilities. The detection of malicious code is becoming increasingly crucial, and current methods of detection require much improvement. This paper proposes a method to advance the detection of malicious code using convolutional neural networks (CNNs) and intelligence algorithm. The CNNs are used to identify and classify grayscale images converted from executable files of malicious code. Non-dominated Sorting Genetic Algorithm II (NSGA-II) is then employed to deal with the data imbalance of malware families. A series of experiments are designed for malware image data from Vision Research Lab. The experimental results demonstrate that the proposed method is effective, maintaining higher accuracy and less loss. • A technique for converting a malware binary to an image was introduced. • In this paper, a method based on CNN is used to identify and classify the malicious codes. • An effective data equilibrium approach based on the NSGA-II was designed. • The proposed method was demonstrated through the extensive experiments. [ABSTRACT FROM AUTHOR]

The virtualization of modern computer networks introduces interesting new opportunities for a more flexible placement of network functions and middleboxes (firewalls, proxies, traffic optimizers, virtual switches, etc.). This paper studies approximation algorithms for the incremental deployment of a minimum number of middleboxes, such that capacity constraints at the middleboxes and length constraints on the communication routes are respected. Based on a new, purely combinatorial and rigorous proof of submodularity, we obtain our main result: a deterministic greedy approximation algorithm which only employs augmenting paths to serve future communication pairs. Hence, our algorithm does not require any changes to the locations of existing middleboxes or the preemption of previously served communication pairs when additional middleboxes are deployed. It is hence particularly attractive for incremental deployments. We prove that the achieved polynomial-time approximation bound is optimal, unless P = NP holds. This paper also initiates the study of a weighted problem variant, in which entire groups of nodes need to communicate via a middlebox, possibly at different rates. We present an LP relaxation and randomized rounding algorithm for this problem, leveraging an interesting connection to scheduling. We complement our formal results with a simulation study of a large set of synthetically generated instances. Our results indicate that the presented algorithms yield near-optimal solutions in practice. [ABSTRACT FROM AUTHOR]

Quality of service (QoS) provision has become an important aspect of high-performance computing interconnection networks. Proof of that is the inclusion of mechanisms targeted to the provision of QoS by the main interconnection technologies such as Gigabit Ethernet, Infiniband (IB) and Omni-Path (OPA). A key component of QoS provision is the output scheduling algorithm, which determines when a packet should be transmitted. An ideal scheduling algorithm should satisfy two main properties: good end-to-end latency and implementation simplicity. Table-based schedulers are able to provide these two properties, and because of this, IB and OPA have implemented this approach. In this paper, we present a comparative study in terms of QoS provision between these two dominating interconnection technologies. Those interconnection technologies are also two examples of non-hierarchical and hierarchical switch architectures, respectively, which gives the results of this study greater significance. In order to carry out the study, the Deficit Table scheduler (DTable) has been used. DTable is a table-based scheduling algorithm which offers a good balance between end-to-end latency and implementation cost. • Implementation and modeling a non-hierarchical and a hierarchical switch. • Description and implementation of QoS Omni-Path and InfiniBand mechanisms. • Adaptation of the Deficit Table Output Scheduler for both architectures. • Comparison of both switch architectures in terms of QoS provision. • Hierarchical architectures have better latency results than non-hierarchical ones. [ABSTRACT FROM AUTHOR]

With the increasing demand for information, the number of nodes in the network is increasing rapidly, followed by the problem of information loss and communication delay caused by insufficient communication. Therefore, how to effectively transmit data and minimize communication delay has been a key issue in networks. In this paper, we first propose a fault-tolerant path algorithm of the k -ary n -cube network Q n k to obtain a fault-free path between any two distinct fault-free nodes with a faulty node set F ⊂ V (Q n k) and | F | ≤ 2 n − 1. Then, we design two algorithms to construct disjoint paths between any two distinct nodes of Q n k without any faults according to whether the two nodes are adjacent or not. Extensive evaluations show that the proposed algorithms has great advantages in average running time. • We propose a fault-tolerant path algorithm of Q n k to obtain a fault-free path between any two distinct fault-free nodes. • We design two algorithms, called DPQ1 and DPQ2, to construct disjoint paths between any two distinct nodes of Q n k. • We compare our algorithms with the algorithm Dijkstra to discuss the average running time and average path length generated by the algorithms. [ABSTRACT FROM AUTHOR]

Graphics Processing Units technology (GPU) and CUDA architecture are one of the most used options to adapt machine learning techniques to the huge amounts of complex data that are currently generated. Biclustering techniques are useful for discovering local patterns in datasets. Those of them that have been implemented to use GPU resources in parallel have improved their computational performance. However, this fact does not guarantee that they can successfully process large datasets. There are some important issues that must be taken into account, like the data transfers between CPU and GPU memory or the balanced distribution of workload between the GPU resources. In this paper, a GPU version of one of the fastest biclustering solutions, BiBit, is presented. This implementation, named gBiBit, has been designed to take full advantage of the computational resources offered by GPU devices. Either using a single GPU device or in its multi-GPU mode, gBiBit is able to process large binary datasets. The experimental results have shown that gBiBit improves the computational performance of BiBit, a CPU parallel version and an early GPU version, called ParBiBit and CUBiBit, respectively. gBiBit source code is available at https://github.com/aureliolfdez/gbibit. • gBiBit is the first binary biclustering method that can process large datasets. • gBiBit development includes a novel methodology to take full advantage of the GPU device resources. • gBiBit solves the memory issues in GPU technology when large datasets must be processed. • gBiBit also has a multi-GPU version that allow to use multiple GPU devices in a balanced way. • gBiBit source code is available at https://github.com/aureliolfdez/gbibit. [ABSTRACT FROM AUTHOR]

Cloud computing provides scalable network services and makes network management more flexible by combining Software-Defined Networking (SDN). Through the northbound interface (e.g., REST API) offered by the SDN controller, users can easily deploy diversified applications to access the network resources. However, exploiting the openness of the northbound interface, malicious applications abuse APIs to launch hostile attacks, which poses serious threats to the network. In this paper, we propose SEAPP, a secure application management framework based on REST API access control. Our main idea is to granularly manage application permissions and encrypt REST API calls to defend against malicious attacks. SEAPP includes two components: 1) permissions detection engine identifies the facticity of application permissions by analyzing permission manifests and byte codes and further identifies the legality of permissions with constructed sensitive API list; 2) registration authorization engine executes encrypted registration between applications and controller by virtue of NTRU algorithm and authorizes applications to call the requested REST APIs based on their risk levels after securely authenticating them. Besides, SEAPP is a lightweight logic architecture between application plane and control plane and supports quick deployment and reconfiguration in runtime. Both theoretical analysis and evaluation results show the security and effectiveness of SEAPP. Besides, SEAPP introduces negligible CPU and memory overheads. • The fidelity and legality of application permissions are identified. • Application registration information is encrypted by NTRU. • A dynamic REST APIs authorization is developed. [ABSTRACT FROM AUTHOR]

Interactive consistency is the problem in which n distinct nodes, each having its own private value, where up to t may be Byzantine, run an algorithm that allows all non-faulty nodes to infer the values of each other node. This problem is relevant to critical applications that rely on the combination of the opinions of multiple peers to provide a service. Examples include monitoring a content source to prevent equivocation or to track variability in the content provided, and resolving divergent state amongst the nodes of a distributed system. Previous works assume a fully synchronous system, where one can make strong assumptions such as negligible message delivery delays and/or detection of absent messages. However, practical, real-world systems are mostly asynchronous, i.e., they exhibit only some periods of synchrony during which message delivery is timely, thus requiring a different approach. In this paper, we present a thorough study of practical interactive consistency. We leverage the vast prior work on broadcast and Byzantine consensus algorithms to design, implement and evaluate a set of randomized algorithms, with only a single synchronization barrier and varying message complexities, that can be used to achieve interactive consistency in real-world distributed systems. We present formal proofs of correctness and message complexity of our proposed algorithms. We provide a complete, open-source implementation of each proposed interactive consistency algorithm by building a multi-layered software stack of algorithms that includes several broadcast algorithms, as well as a binary and a multi-valued consensus algorithm. Most of these algorithms have never been implemented and evaluated in a real system before. Finally, we analyze the performance of our suite of algorithms experimentally by testing both single instance and multiple parallel instances of each alternative and present a case study of achieving interactive consistency in a real-world distributed e-voting system. • Algorithms for interactive consistency in practical, real-world systems. • Formal proofs of correctness for the proposed algorithms. • Open-source implementation of the proposed algorithms. • Empirical evaluation of open-source prototype and e-voting case study. [ABSTRACT FROM AUTHOR]

With the advent of the Industry 4.0 era, the development of smart cities based on the Internet of Things (IoT) has reached a new level. As a key component of the Internet of Things (IoT), the security of wireless sensor networks (WSN) has received widespread attention. Among them, Energy Internet, as an important part to support the construction of smart cities, its security and reliability research is becoming more and more important. In the Energy Internet, distributed energy transaction model is a promising approach to replace the traditional centralized transaction model and has become the leading direction of development in energy trading. As the underlying support, blockchain technology is attracting more and more attention due to its advantages, i.e., integrity and non-repudiation. However, most blockchain-based trading models face the problem of privacy disclosure. In this paper, to solve this problem, Ciphertext-Policy Attribute-Based Encryption (CP-ABE) is introduced as the core algorithm to reconstruct the transaction model. Specifically, we build a general model for distributed transactions called PP-BCETS (Privacy-preserving Blockchain Energy Trading Scheme). It can achieve fine-grained access control through transaction arbitration in the ciphertext form. This design can maximize the protection of privacy information, and considerably improve the security and reliability of the transaction model. Additionally, a credibility-based equity proof consensus mechanism is proposed in PP-BCETS, which can greatly increase the operation efficiency. The security analysis and experimental evaluations are conducted to prove the validity and practicability of our proposed scheme. • Secure and privacy-preserving energy trading scheme is proposed. • ABE- and blockchain-based energy trading. • credibility-based equity proof consensus mechanism. [ABSTRACT FROM AUTHOR]

Rendezvous algorithms encode a communication pattern that is useful when processors sending data do not know who the receiving processors should be, or vice versa. The idea is to define an intermediate decomposition where datums from different sending processors can "rendezvous" to perform a computation, in a manner that both the senders and eventual receivers of the results can identify the appropriate rendezvous processor. Originally designed for interpolating between overlaid grids with independent parallel decompositions (Plimpton et al., 2004), we have recently found rendezvous algorithms useful for a variety of operations in particle- or grid-based simulation codes when running large problems on large numbers of processors. In particular, we show they can perform well when a load-balanced intermediate decomposition is randomized and not spatial, requiring all-to-all communication to move data between processors. In this case rendezvous algorithms leverage the large bisection communication bandwidths which parallel machines provide. We describe how rendezvous algorithms work in a scientific computing context and give specific examples for molecular dynamics and Direct Simulation Monte Carlo codes which result in dramatic performance improvements versus simpler algorithms which do not scale as well. We explain how a generic rendezvous algorithm can be implemented, and also point out similarities with the MapReduce paradigm popularized by Google and Hadoop. • This paper explains how parallel rendezvous algorithms work in the context of large-scale scientific modeling and simulation codes. • It gives several examples of such algorithms. • It presents performance gains of the new algorithms relative to previously used simpler algorithms which were less scalable. [ABSTRACT FROM AUTHOR]

Fog computing is an emerging paradigm that brings computing capabilities closer to distributed IoT devices, which provides networking services between end devices and traditional cloud data centers. One important mission is to further reduce the monetary cost of fog resources while meeting the ever-growing demands of multiple users. In this paper, we focus on minimizing the total cost for multiple mobile users to provide an efficient resource provisioning scheme in fog computing. The total cost includes two aspects: the replication cost and the transmission cost. We consider three cases for the resource provision problem by focusing on different cost models. First, one simple case where users can only upload one replication is discussed, and an optimal solution is proposed by converting the original problem into a bipartite graph matching. Then we consider a more complicated case in which each user can upload multiple replications on fog nodes in the resource provisioning. Specifically, two models are discussed: the 0–1 transmission cost model and the different transmission cost model. For the 0–1 transmission cost model, each user can upload multiple replications with a constant transmission cost, and one optimal greedy solution is proposed. For the different transmission cost model, the transmission cost is related to the distance of each pair of fog nodes. This problem is proven to be NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. Extensive simulations also prove the efficiency of our schemes. • We consider the resource provision problem for users with cost minimization and model the identified problem by considering two types of cost: replication cost and transmission cost. We first discuss a simple case, and one optimal solution is proposed. We then consider a more complicated case in which each user can upload multiple replications on fog nodes in the provisioning process. Two models are discussed: the 0–1 transmission cost model and the different transmission cost model. • We propose an optimal solution for the 0–1 transmission cost model. Then we prove that the problem under the different transmission cost model is NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. • Various simulations were conducted to compare our joint optimization methods with several state-of-the-art ones based on two real datasets: the Mobike dataset and the Microsoft GPS trajectory dataset. The results are shown from different perspectives to provide conclusions. [ABSTRACT FROM AUTHOR]

Large-scale data-intensive applications provide services to users by routing service requests to geographically distributed data centers interconnected by Internet links. In order to achieve good reliability and data access latency performance, cloud service providers often simultaneously place multiple copies of the data in different data centers. The network communication required for updating the multiple data copies incurs an operational cost. At the same time, the penalty incurred by the Service Level Agreement (SLA) violation for data access from the data centers also imposes an operational cost on the service providers. In this paper, we tackle the problem of data placement in distributed data centers with the aim to minimize the operational cost incurred by delay SLA violation penalty and inter-data center network communication, assuming each data has K data replicas. We propose a K-level Cluster-based Data Placement algorithm (K-CDP) for the problem. The algorithm solves the linear programming relaxation and dual programming problems corresponding to the problem of minimizing SLA violation penalty cost caused by placing a replica of each data in a data center. Based on the obtained solutions, the algorithm clusters the data so that the data with similar placeable data centers form a data cluster. For the data in each cluster, the algorithm selects K data centers to minimize the operational cost. We prove that algorithm K-CDP is 2-approximation to the data placement problem. Our simulation results demonstrate that the proposed algorithm can effectively reduce the penalty cost incurred by delay SLA violation, the network communication cost, and the operational cost of data centers. • We tackle the data placement problem to minimize SLA violation and network communication cost. • We propose an algorithm which is proved to be 2-approximation to the data placement problem. • The simulation results show the proposed algorithm is effective and promising. [ABSTRACT FROM AUTHOR]

Stochastic gradient descent (SGD) is a popular stochastic optimization method in machine learning. Traditional parallel SGD algorithms, e.g., SimuParallel SGD (Zinkevich, 2010), often require all nodes to have the same performance or to consume equal quantities of data. However, these requirements are difficult to satisfy when the parallel SGD algorithms run in a heterogeneous computing environment; low-performance nodes will exert a negative influence on the final result. In this paper, we propose an algorithm called weighted parallel SGD (WP-SGD). WP-SGD combines weighted model parameters from different nodes in the system to produce the final output. WP-SGD makes use of the reduction in standard deviation to compensate for the loss from the inconsistency in performance of nodes in the cluster, which means that WP-SGD does not require that all nodes consume equal quantities of data. We also propose the methods of running two other parallel SGD algorithms combined with WP-SGD in a heterogeneous environment. The experimental results show that WP-SGD significantly outperforms the traditional parallel SGD algorithms on distributed training systems with an unbalanced workload. • We propose WP-SGD which is used in distribution system with unbalanced workloads. • WP-SGD tolerate a large delay in a cluster with an exponentially decreasing weight. • WP-SGD helps other parallel SGD algorithms work on unbalanced workloads systems. • We use experiments to show the advantages of WP-SGD on workloads unbalanced systems. [ABSTRACT FROM AUTHOR]

The K-means algorithm is one of the most popular algorithms in Data Science, and it is aimed to discover similarities among the elements belonging to large datasets, partitioning them in K distinct groups called clusters. The main weakness of this technique is that, in real problems, it is often impossible to define the value of K as input data. Furthermore, the large amount of data used for useful simulations makes impracticable the execution of the algorithm on traditional architectures. In this paper, we address the previous two issues. On the one hand, we propose a method to dynamically define the value of K by optimizing a suitable quality index with special care to the computational cost. On the other hand, to improve the performance and the effectiveness of the algorithm, we propose a strategy for parallel implementation on modern multicore CPUs. • For several problems the number of clusters in the K-means algorithm is unavailable. • Adaptive strategies enhance the performance of the K-means algorithm. • Parallel implementation is mandatory for large clustering problems. [ABSTRACT FROM AUTHOR]

Clustering, which explores the visualization and distribution of data, has recently been studied widely. Although the existing clustering algorithms can well detect arbitrary shape clusters, most of them face the limitation that they cluster points on the basis of two physical metrics, distance and density, but ignore the orientation relationship of data distribution. Beside, they have a difficulty of selecting suitable parameters, which are important inputs of the clustering algorithms. In this paper, we firstly introduce a new physical metric, namely direction. Then, based on this new metric, we propose an adaptive direction-based clustering algorithm, namely ADC, which can automatically calculate appropriate parameters. Finally, we develop a parallel ADC algorithm based on multi-processors to improve the performance of the ADC algorithm. Compared with other clustering algorithms, experimental results demonstrate that the proposed algorithms are more general and can get much better clustering results. In addition, the parallel ADC algorithm has the best scalability over large data sets. • A new physical metric, direction, has been considered in the proposed clustering algorithm. • Adaptive strategies can obtain the parameter automatically. • A parallel algorithm PADC is proposed based on multi-core. • The experimental results demonstrate that the proposed PADC algorithm can efficiently process very large scale data sets with a good performance. [ABSTRACT FROM AUTHOR]

Finding connected components is one of the most widely used operations on a graph. Optimal serial algorithms for the problem have been known for half a century, and many competing parallel algorithms have been proposed over the last several decades under various different models of parallel computation. This paper presents a class of parallel connected-component algorithms designed using linear-algebraic primitives. These algorithms are based on a PRAM algorithm by Shiloach and Vishkin and can be designed using standard GraphBLAS operations. We demonstrate two algorithms of this class, one named LACC for Linear Algebraic Connected Components, and the other named FastSV which can be regarded as LACC's simplification. With the support of the highly-scalable Combinatorial BLAS library, LACC and FastSV outperform the previous state-of-the-art algorithm by a factor of up to 12x for small to medium scale graphs. For large graphs with more than 50B edges, LACC and FastSV scale to 4K nodes (262K cores) of a Cray XC40 supercomputer and outperform previous algorithms by a significant margin. This remarkable performance is accomplished by (1) exploiting sparsity that was not present in the original PRAM algorithm formulation, (2) using high-performance primitives of Combinatorial BLAS, and (3) identifying hot spots and optimizing them away by exploiting algorithmic insights. [ABSTRACT FROM AUTHOR]

By increasing mobile devices in technology and human life, using a runtime and mobile services has gotten more complex along with the composition of a large number of atomic services. Different services are provided by mobile cloud components to represent the non-functional properties as Quality of Service (QoS), which is applied by a set of standards. On the other hand, the growth of the energy-source heterogeneity in mobile clouds is an emerging challenge according to the energy saving problem in mobile nodes. In order to mobile cloud service composition as an NP-Hard problem, an efficient selection method should be taken by problem using optimal energy-aware methods that can extend the deployment and interoperability of mobile cloud components. Also, an energy-aware service composition mechanism is required to preserve high energy saving scenarios for mobile cloud components. In this paper, an energy-aware mechanism is applied to optimize mobile cloud service composition using a hybrid Shuffled Frog Leaping Algorithm and Genetic Algorithm (SFGA). Experimental results capture that the proposed mechanism improves the feasibility of the service composition with minimum energy consumption, response time, and cost for mobile cloud components against some current algorithms. [ABSTRACT FROM AUTHOR]