PageRank is a well-known centrality measure for the web used in search engines, representing the importance of each web page. In this paper, we develop a new class of distributed algorithms for the computation of Page...
详细信息
ISBN:
(纸本)9781538654286
PageRank is a well-known centrality measure for the web used in search engines, representing the importance of each web page. In this paper, we develop a new class of distributed algorithms for the computation of PageRank. Each page computes its own PageRank value by interacting with pages connected over hyperlinks Our approach is based on a simple but novel interpretation of PageRank. Gossip type randomization is employed in the update schemes, and it is shown that the page selection need not be limited to the uniform distribution. In comparison with other existing techniques, significant advantages can be seen in their convergence performance as demonstrated via numerical examples.
We consider the distributed optimization problem in which a network of agents aims to minimize the average of local functions. To solve this problem, several algorithms have recently been proposed where agents perform...
详细信息
ISBN:
(纸本)9781538679012;9781538679265
We consider the distributed optimization problem in which a network of agents aims to minimize the average of local functions. To solve this problem, several algorithms have recently been proposed where agents perform various combinations of communication with neighbors, local gradient computations, and updates to local state variables. In this paper, we present a canonical form that characterizes any first-order distributed algorithm that can be implemented using a single round of communication and gradient computation per iteration, and where each agent stores up to two state variables. The canonical form features a minimal set of parameters that are both unique and expressive enough to capture any distributed algorithm in this class. The generic nature of our canonical form enables the systematic analysis and design of distributed optimization algorithms.
distributed algorithms provide flexibility over centralized algorithms for resource allocation problems, e.g., cyber-physical systems. However, the distributed nature of these algorithms often makes the systems suscep...
详细信息
ISBN:
(数字)9781728113982
ISBN:
(纸本)9781728113999
distributed algorithms provide flexibility over centralized algorithms for resource allocation problems, e.g., cyber-physical systems. However, the distributed nature of these algorithms often makes the systems susceptible to man-in-the-middle attacks, especially when messages are transmitted between price-taking agents and a central coordinator. We propose a resilient strategy for distributed algorithms under the framework of primal-dual distributed optimization. We formulate a robust optimization model that accounts for Byzantine attacks on the communication channels between agents and coordinator. We propose a resilient primal-dual algorithm using state-of-the-art robust statistics methods. The proposed algorithm is shown to converge to a neighborhood of the robust optimization model, where the neighborhood's radius is proportional to the fraction of attacked channels.
This paper presents the first (non-trivial) distributed planar embedding algorithm. We consider this a crucial first step in a broader program to design efficient distributed algorithms for planar networks. We work in...
详细信息
ISBN:
(纸本)9781450339643
This paper presents the first (non-trivial) distributed planar embedding algorithm. We consider this a crucial first step in a broader program to design efficient distributed algorithms for planar networks. We work in the standard distributed model in which nodes can send an O (log n)-bit message to each of their neighbors per round. In a planar network, with n nodes and diameter D, our deterministic planar embedding algorithm uses O (D . min{log n, D}) rounds to compute a combinatorial planar embedding, which consists of each node knowing the clockwise order of its incident edges in a fixed planar drawing. The complexity of our algorithm is near-optimal and matches the trivial lower bound of Omega(D) up to a log n factor. No algorithm outperforming the trivial round complexity of O(n) was known prior to this work.
This article describes a very high-level language for clear description of distributed algorithms and optimizations necessary for generating efficient implementations. The language supports high-level control flows in...
详细信息
This article describes a very high-level language for clear description of distributed algorithms and optimizations necessary for generating efficient implementations. The language supports high-level control flows in which complex synchronization conditions can be expressed using high-level queries, especially logic quantifications, over message history sequences. Unfortunately, the programs would be extremely inefficient, including consuming unbounded memory, if executed straightforwardly. We present new optimizations that automatically transform complex synchronization conditions into incremental updates of necessary auxiliary values as messages are sent and received. The core of the optimizations is the first general method for efficient implementation of logic quantifications. We have developed an operational semantics of the language, implemented a prototype of the compiler and the optimizations:, and successfully used the language and implementation on a variety of important distributed algorithms.
This letter establishes a general theorem concerning the eigenvalue invariance of certain inhomogeneous matrix products with respect to changes of individual multiplicands' orderings. Instead of detailed entries, ...
详细信息
This letter establishes a general theorem concerning the eigenvalue invariance of certain inhomogeneous matrix products with respect to changes of individual multiplicands' orderings. Instead of detailed entries, it is the zero-nonzero structure that matters in determining such eigenvalue invariance. The theorem is then applied in analyzing the convergence rate of a distributed algorithm for solving linear equations over networks modeled by undirected graphs.
Brain-Computer Interfaces (BCIs) have become a research field with interesting applications, and it can be inferred from published papers that different persons activate different parts of the brain to perform the sam...
详细信息
Brain-Computer Interfaces (BCIs) have become a research field with interesting applications, and it can be inferred from published papers that different persons activate different parts of the brain to perform the same action. This paper presents a personalized interface design method, for electroencephalogram-(EEG-) based BCIs, based on channel selection. We describe a novel two-step method in which firstly a computationally inexpensive greedy algorithm finds an adequate search range;and, then, an Estimation of Distribution Algorithm(EDA) is applied in the reduced range to obtain the optimal channel subset. The use of the EDA allows us to select the most interacting channels subset, removing the irrelevant and noisy ones, thus selecting the most discriminative subset of channels for each user improving accuracy. The method is tested on the IIIa dataset from the BCI competition III. Experimental results show that the resulting channel subset is consistent with motor-imaginary-related neurophysiological principles and, on the other hand, optimizes performance reducing the number of channels.
We propose distributed algorithms for two well-established problems that operate efficiently under extremely harsh conditions. Our algorithms achieve state-of-the-art performance in a simple and novel way. Our algorit...
详细信息
We propose distributed algorithms for two well-established problems that operate efficiently under extremely harsh conditions. Our algorithms achieve state-of-the-art performance in a simple and novel way. Our algorithm for maximal independent set selection operates on a network of identical anonymous processors. The processor at each node has no prior information about the network. At each time step, each node can only broadcast a single bit to all its neighbours, or remain silent. Each node can detect whether one or more neighbours have broadcast, but cannot tell how many of its neighbours have broadcast, or which ones. We build on recent work of Afek et al. (Science 331(6014):183-185, 2011) which was inspired by studying the development of a network of cells in the fruit fly. However we incorporate for the first time another important feature of the biological system: varying the probability value used at each node based on local feedback from neighbouring nodes. Given any n-node network, our algorithm achieves with high probability the optimal time complexity of rounds and the optimal expected message complexity of O(1) single-bit messages broadcast by each node. We also show that the previous approach, without feedback, cannot achieve better than time complexity with high probability, whatever global scheme is used to choose the probabilities. Our algorithm for distributed greedy colouring works under similar harsh conditions: each identical node has no prior information about the network, can only broadcast a single message to all neighbours at each time step representing a desired colour, and can only detect whether at least one neighbour has broadcast each colour value. We show that with high probability our algorithm has a time complexity of , where is the maximum degree of the network, and also has an expected message complexity of O(1) messages broadcast by each node.
The arrival of smaIl-scale distributed energy generation in the future smart grid has led to the emergence of so-called prosumers, who can both consume as weIl as produce energy. By using local generation from renewab...
详细信息
ISBN:
(纸本)9781509040759
The arrival of smaIl-scale distributed energy generation in the future smart grid has led to the emergence of so-called prosumers, who can both consume as weIl as produce energy. By using local generation from renewable energy resources, the stress on power generation and supply system can be significantly reduced during high demand periods. However, this also creates a significant challenge for conventional power plants that suddenly need to ramp up quickly when the renewable energy drops off. In this paper, we propose an energy consumption scheduling problem tor prosumers to minimize the peak ramp of the system. The optimal schedule of prosumers can be obtained by solving the centralized optimization problem. However, due to the privacy concerns and the distributed topology of the power system, the centralized design is difficult to implement in practice. Therefore, we propose the distributed algorithms to efficiently solve the centralized problem using the alternating direction method of multiplier (ADMM), in which each prosumer independently schedules its energy consumption profile. The simulation results demonstrate the convergence performance of the proposed algorithms as weIl as the capability of our model in reducing the peak ramp of the system.
Efficient deployment algorithms are developed in this paper to increase the coverage area in a network of wireless mobile sensors. The proposed strategies iteratively compute the new candidate position of each sensor ...
详细信息
Efficient deployment algorithms are developed in this paper to increase the coverage area in a network of wireless mobile sensors. The proposed strategies iteratively compute the new candidate position of each sensor based on the existing coverage holes. These holes are obtained using a Voronoi diagram for the case of sensors with the same sensing ranges, and a multiplicatively weighted Voronoi (MW-Voronoi) diagram for the case of sensors with different sensing ranges. Each sensor is driven by some virtual forces which are applied to it from the vertices and boundaries of its Voronoi cell. These forces are obtained in such a way that when the sensor is relocated, the covered area of the corresponding cell increases. Simulation results demonstrate the efficacy of the proposed strategies, and their superiority to existing algorithms.
暂无评论