Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in {-1, 1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node...
详细信息
ISBN:
(纸本)9781510836358
Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in {-1, 1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting.
When a vast number of camera sensors are randomly placed in a target field, how can we produce a sleep/activate schedule for camera sensors to maximize the lifetime of target coverage in the target field? This well-kn...
详细信息
When a vast number of camera sensors are randomly placed in a target field, how can we produce a sleep/activate schedule for camera sensors to maximize the lifetime of target coverage in the target field? This well-known problem is called Maximum Lifetime Coverage Problem (MLCP), which has been explored extensively in the literature. However, MLCP in full-view coverage camera sesnor networks are far more complicated since each target should be full-view covered by a group of camera sensors instead of a single sensor as in conventional scenarios. In this paper we address the full-view covered target problem, with the objective of maximizing the lifetime of a power constrained camera sensor network deployed for full-view coverage of targets with known location. We consider that a large number of camera sensors are placed randomly in close proximity of targets and each camera sensor sends the collected data to a base station. We define the camera sensor network lifetime as the time interval the targets are full-view covered by a camera sensor cover. Our contributions include: (1) an efficient data structure to represent a family of camera sensor cover, each of which full-view cover all targets with consideration of the lifetime of each camera sensor; (2) an energy efficient monitoring scheme where only the camera sensors from the current active set are responsible for monitoring all targets and for transmitting the collected data, while all other camera sensors are in a low-energy sleep mode; (3) formulating the maximizing camera sensor network lifetime problem into a packing linear programming problem, where a modified Garg-Konemann Algorithm to find the near optimal solution is applied.
Dynamic networks are characterized by frequent topology changes due to the unpredictable appearance and disappearance of mobile devices and/or communication links. In this paper, we propose a correct-by-construction a...
详细信息
Dynamic networks are characterized by frequent topology changes due to the unpredictable appearance and disappearance of mobile devices and/or communication links. In this paper, we propose a correct-by-construction approach for proving distributed algorithms in a forest of spanning trees. Our approach consists in two phases. The first one aims to control the dynamic structure of the network by triggering a maintenance operation when the forest is altered. To do so, we develop a formal pattern using the Event-B method which is based on an existing model for building and maintaining a spanning forest in dynamic networks. The second phase of our approach deals with distributed algorithms which can be applied to spanning trees. We illustrate our pattern through an example of a leader election algorithm. The proof statistics show that our solution can save efforts on specifying as well as proving the correctness of distributed algorithms in a forest of spanning trees.
The optimal power flow (OPF) problem, a fundamental problem in power systems, is generally nonconvex and computationally challenging for networks with an increasing number of smart devices and real-time control requir...
详细信息
ISBN:
(纸本)9781509045839
The optimal power flow (OPF) problem, a fundamental problem in power systems, is generally nonconvex and computationally challenging for networks with an increasing number of smart devices and real-time control requirements. In this paper, we first investigate a fully distributed approach by means of the augmented Lagrangian and proximal alternating minimization method to solve the nonconvex OPF problem with a convergence guarantee. Given time-critical requirements, we then extend the algorithm to a distributed parametric tracking scheme with practical warm-starting and termination strategies, which aims to provide a closed-loop sub-optimal control policy while taking into account the grid information updated at the time of decision making. The effectiveness of the proposed algorithm for real-time nonconvex OPF problems is demonstrated in numerical simulations.
This paper studies iterative distributed algorithms for real-time available transfer capability (ATC) assessment in energy management systems of multiarea power systems. Since ATC calculations can be modeled as a spec...
详细信息
ISBN:
(纸本)9781538622131;9781538622124
This paper studies iterative distributed algorithms for real-time available transfer capability (ATC) assessment in energy management systems of multiarea power systems. Since ATC calculations can be modeled as a special nonlinear optimal power-flow problem, iterative decomposition-coordination approaches based on constrained augmented Lagrangian methods can be applied. One special distributed scheme, called the auxiliary problem principle method, will be studied for distributed ATC assessment in this paper. A computation framework of this distributed algorithm is investigated. System partition with nonoverlapping and boundary sub-systems will also be studied. Simulations of several IEEE test systems will be conducted to validate the feasibility and the correctness of this distributed ATC. In addition, the real-time monitoring and reaction mechanism of this distributed algorithm will also be demonstrated by numerical experiments.
Packet scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we study packet routing and sche...
详细信息
Packet scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we study packet routing and scheduling under this model of interference. The main focus of our work is the development of fully distributed (decentralized) protocols. We present polylogarithmic/constant factor approximation algorithms for various families of disk graphs (which capture the geometric nature of wireless-signal propagation), as well as near-optimal approximation algorithms for general graphs. A basic distributed coloring procedure, originally due to Luby [1993] (Journal of Computer and System Sciences, 47:250-286, 1993), underlies many of our algorithms. The work of Finocchi et al. [2002] (Proc. ACM-SIAM Symposium on Discrete algorithms, 2002) showed that a natural modification of this algorithm leads to improved performance. A rigorous explanation of this was left as an open question, and we prove that the modified algorithm is indeed provably better in the worst case.
Proving the correctness of distributed algorithms in dynamic networks is a hard task due to the time complexity and the highly dynamic behavior. In the literature, the existing solutions lack a consensus about their d...
详细信息
ISBN:
(纸本)9781509016631
Proving the correctness of distributed algorithms in dynamic networks is a hard task due to the time complexity and the highly dynamic behavior. In the literature, the existing solutions lack a consensus about their developments and their proofs. Moreover, the proofs which have been presented are done manually. In this paper, we propose a reuse based approach for specifying and proving distributed algorithms in dynamic networks. It consists in developing a formal pattern using Event-B method, based on refinement techniques. The proposed pattern allows to handle topological events in dynamic networks and to characterize the concept of time. Our solution relies on evolving graphs as a powerful model to record the evolution of a network topology. To illustrate it, we present an example of a distributed counting algorithm. The proof statistics related to the development of the pattern and the algorithm show the efficiency of our solution.
In this article we study statistical properties of a commonly used network model - an Erdos-Renyi random graph G(n, p). We are interested in the performance of distributed algorithms on large networks, which might be ...
详细信息
In this article we study statistical properties of a commonly used network model - an Erdos-Renyi random graph G(n, p). We are interested in the performance of distributed algorithms on large networks, which might be represented by G(n, p). We concentrate on classical problems from the field of distributed algorithms such as: finding a maximal independent set, a vertex colouring, an approximation of a minimum dominating set, a maximal matching, an edge colouring and an approximation of a maximum matching. We propose new algorithms, which with probability close to one as n -> infinity construct anticipated structures in G(n, p) in a low number of rounds. Moreover, in some cases, we modify known algorithms to obtain better efficiency on G(n, p). (C) 2015 Elsevier B.V. All rights reserved.
This paper studies a class of network optimization problems where the objective function is the summation of individual agents' convex functions and their decision variables are coupled by linear equality constrai...
详细信息
ISBN:
(纸本)9781509045518
This paper studies a class of network optimization problems where the objective function is the summation of individual agents' convex functions and their decision variables are coupled by linear equality constraints. These constraints are not sparse, meaning that they do not match the pattern of the network adjacency matrix. We propose two approaches to design efficient distributed algorithms to solve the network optimization problem. Our first approach consists of transforming the non-sparse equality constraints into sparse ones by increasing the number of the agents' decision variables, yielding an exact reformulation of the original optimization problem. We discuss two reformulations, based on the addition of consensus variables and of constraint-mismatch variables, and discuss the scalability of the strategies resulting from them. Our second approach consists instead of sparsifying the non-sparse constraints by zeroing some coefficients, yielding an approximate reformulation of the original problem. We formally characterize the gap on the distance between the optimizers of the original and approximated problems as a function of the number of entries made zero in the constraints. Various simulations illustrate our results.
This paper introduces the concept of low-congestion shortcuts for (near-)planar networks, and demonstrates their power by using them to obtain near-optimal distributed algorithms for problems such as Minimum Spanning ...
详细信息
ISBN:
(纸本)9781611974331
This paper introduces the concept of low-congestion shortcuts for (near-)planar networks, and demonstrates their power by using them to obtain near-optimal distributed algorithms for problems such as Minimum Spanning Tree (MST) or Minimum Cut, in planar networks. Consider a graph G = (V, E) and a partitioning of V into subsets of nodes S_1, ..., S_N, each inducing a connected subgraph G[S_i]. We define an α-congestion shortcut with dilation β to be a set of subgraphs H_1, ..., H_N {is contained in} G, one for each subset S_i, such that 1. For each i ∈ [1, N], the diameter of the subgraph G[S_i] + H_i is at most β. 2. For each edge e ∈ E, the number of subgraphs G[S_i] + H_i containing e is at most α. We prove that any partition of a D-diameter planar graph into individually-connected parts admits an O(D log D)-congestion shortcut with dilation O(DlogD), and we also present a distributed construction of it in O(D) rounds. We moreover prove these parameters to be near-optimal;i.e., there are instances in which, unavoidably, max{α, β} = Ω(D (log D)/(log log D)). Finally, we use low-congestion shortcuts, and their efficient distributed construction, to derive O(D)-round distributed algorithms for MST and Min-Cut, in planar networks. This complexity nearly matches the trivial lower bound of Ω(D). We remark that this is the first result bypassing the well-known Ω(D+{the square root of}n) existential lower bound of general graphs (see Peleg and Rubinovich [FOCS'99];Elkin [STOC'04];and Das Sarma et al. [STOC'11]) in a family of graphs of interest.
暂无评论