Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as h-length flows which are defined as flows whose flow ...
详细信息
ISBN:
(纸本)9781450399135
Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as h-length flows which are defined as flows whose flow paths have length at most h. Many well-studied algorithmic primitives-such as maximal and maximum length-constrained disjoint paths-are special cases of h-length flows. Likewise the optimal h-length flow is a fundamental quantity in network optimization, characterizing, up to poly-log factors, how quickly a network can accomplish numerous distributed primitives. In this work, we give the first efficient algorithms for computing (1 - epsilon)-approximate h-length flows that are nearly "as integral as possible." We give deterministic algorithms that take (O) over tilde (poly(h, 1/epsilon)) parallel time and (O) over tilde (poly(h, 1/epsilon) center dot 2(O) (root log n)) distributed CONGEST time. We also give a CONGEST algorithm that succeeds with high probability and only takes (O) over tilde (poly(h, 1/epsilon)) time. Using our h-length flow algorithms, we give the first efficient deterministic CONGEST algorithms for the maximal disjoint paths problem with length constraints-settling an open question of Chang and Saranurak (FOCS 2020)-as well as essentially-optimal parallel and distributed approximation algorithms for maximum length-constrained disjoint paths. The former greatly simplifies deterministic CONGEST algorithms for computing expander decompositions. We also use our techniques to give the first efficient and deterministic (1-epsilon)-approximation algorithms for bipartite b-matching in CONGEST. Lastly, using our flow algorithms, we give the first algorithms to efficiently compute h-length cutmatches, an object at the heart of recent advances in length-constrained expander decompositions.
Conventional infrastructures based on the cloud are not sufficient for the emerging Internet of Things (IoT) applications requirements. Many big problems are shortcomings, especially in terms of network bandwidth and ...
详细信息
Conventional infrastructures based on the cloud are not sufficient for the emerging Internet of Things (IoT) applications requirements. Many big problems are shortcomings, especially in terms of network bandwidth and latency. Throughout recent years, the idea to relieve fog computing and edge computing was suggested by bringing data processing capacities closer to these limits to the edge of the network. The authors assume that the full potential of IoT will, in many cases, only be activated by the combination of cloud, fog, and edge computing in a new computing paradigm, given IoT growth and development forecasts. This article discusses the possibility and need for such a paradigm by introducing steam computing as a new distributed type of computing using cloud, fog, and edge utilities to carry out data processing and storage. The authors treat steam computing through four planes: security and privacy plane, data analytics and fault tolerance plane and deployment and test beds plane. Finally, the authors focus on the open issues and future trends in steam computing.
We present randomized distributed algorithms for the maximal independent set problem (MIS) that, while keeping the time complexity nearly matching the best known, reduce the energy complexity substantially. These algo...
详细信息
ISBN:
(纸本)9798400701214
We present randomized distributed algorithms for the maximal independent set problem (MIS) that, while keeping the time complexity nearly matching the best known, reduce the energy complexity substantially. These algorithms work in the standard CONGEST model of distributed message passing with O (log n) bit messages. The time complexity measures the number of rounds in the algorithm. The energy complexity measures the number of rounds each node is awake;during other rounds, the node sleeps and cannot perform any computation or communications. Our first algorithm has an energy complexity of O (log log n) and a time complexity of O ( log(2) n). Our second algorithm is faster but slightly less energy-efficient: it achieves an energy complexity of O (log(2) log n) and a time complexity of O (log n center dot log log n center dot log* n). Thus, this algorithm nearly matches the O (log n) time complexity of the state-of-the-art MIS algorithms while significantly reducing their energy complexity from O (log n) to O ( log(2) log n).
In this paper, we propose a distributed stochastic first-order method for saddle point problems over strongly connected graphs. Existing methods generally suffer from a steady-state error that arises due to the hetero...
详细信息
ISBN:
(纸本)9798350301243
In this paper, we propose a distributed stochastic first-order method for saddle point problems over strongly connected graphs. Existing methods generally suffer from a steady-state error that arises due to the heterogeneous nature of data distribution (captured by the local versus global cost gaps) and the variance of the stochastic gradients. We propose GT-SGDA, a distributed stochastic gradient descent ascent method that uses network-level gradient tracking to eliminate the steady-state error component due to the local versus global cost gap. We show that GT-SGDA converges linearly to an error ball around the unique saddle point for sufficiently small constant step-sizes when the global cost is strongly concave-convex (a necessary condition for the existence of a unique saddle point). Moreover, we show that the size of this error ball depends on the variance of the stochastic gradients. We provide numerical experiments to illustrate the convergence properties of GT-SGDA for different applications and highlight the significance of gradient tracking. We also show the performance of GT-SGDA for training modern applications like distributed generative adversarial networks (GANs).
This brief analyzes the robust secure consensus control problem for linear multi-agent systems under random Denial-of-Service (DoS) attacks and external disturbances. When agents communicate with its neighbors, a mali...
详细信息
This brief analyzes the robust secure consensus control problem for linear multi-agent systems under random Denial-of-Service (DoS) attacks and external disturbances. When agents communicate with its neighbors, a malicious attacker randomly carries out DoS attacks to certain communication channels in the network, thereby causing the communication topology to be Markovian switching. Solely depending on the immediate partial information per node rather than global information, a fully distributed robust secure consensus protocol is put forward under DoS attacks and external disturbances by using the Lyapunov function analysis. A simulation case of leader-follower formation is taken to explain the efficiency of the consensus algorithm.
The history of the alternating projection method for finding a common point of several convex sets in Euclidean space goes back to the well-known Kaczmarz algorithm for solving systems of linear equations, which was d...
详细信息
The history of the alternating projection method for finding a common point of several convex sets in Euclidean space goes back to the well-known Kaczmarz algorithm for solving systems of linear equations, which was devised in the 1930s and later found wide applications in image processing and computed tomography. An important role in the study of this method was played by I.I. Eremin's, L.M. Bregman's, and B.T. Polyak's works, which appeared nearly simultaneously and contained general results concerning the convergence of alternating projections to a point in the intersection of sets, assuming that this intersection is nonempty. In this paper, we consider a modification of the convex set intersection problem that is related to the theory of multi-agent systems and is called the constrained consensus problem. Each convex set in this problem is associated with a certain agent and, generally speaking, is inaccessible to the other agents. A group of agents is interested in finding a common point of these sets, that is, a point satisfying all the constraints. distributed analogues of the alternating projection method proposed for solving this problem lead to a rather complicated nonlinear system of equations, the convergence of which is usually proved using special Lyapunov functions. A brief survey of these methods is given, and their relation to the theorem ensuring consensus in a system of averaging inequalities recently proved by the second author is shown (this theorem develops convergence results for the usual method of iterative averaging as applied to the consensus problem).
We provide the first deterministic distributed synchronizer with near-optimal time complexity and message complexity overheads. Concretely, given any distributed algorithm A that has time complexity.. and message comp...
详细信息
ISBN:
(纸本)9798400701214
We provide the first deterministic distributed synchronizer with near-optimal time complexity and message complexity overheads. Concretely, given any distributed algorithm A that has time complexity.. and message complexity.. in the synchronous message-passing model (subject to some care in defining the model), the synchronizer provides a distributed algorithm A' that runs in the asynchronous message-passing model with time complexity T . poly(log n) and message complexity (M + m) . poly(log n). Here, n and m denote the number of nodes and edges in the network, respectively. The synchronizer is deterministic in the sense that if algorithm A is deterministic, then so is algorithm A'. Previously, only a randomized synchronizer with near-optimal overheads was known by seminal results of Awerbuch, Patt-Shamir, Peleg, and Saks [STOC 1992] and Awerbuch and Peleg [FOCS 1990]. We also point out and fix some inaccuracies in these prior works. As concrete applications of our synchronizer, we resolve some longstanding and fundamental open problems in distributed algorithms: we get the first asynchronous deterministic distributed algorithms with near-optimal time and message complexities for leader election, breadth-first search tree, and minimum spanning tree computations: these all have message complexity (O) over tilde (m) message complexity. The former two have (O) over tilde (D) time complexity, where D denotes the network diameter, and the latter has (O) over tilde (D + root n) time complexity. All these bounds are optimal up to logarithmic factors. Previously all such near-optimal algorithms were either restricted to the synchronous setting or required randomization.
This paper studies the dynamic average consensus problem of multi-agent systems under event-triggered communication. In this problem, each agent has access to a time-varying reference signal and aims to track the aver...
详细信息
ISBN:
(纸本)9798350301243
This paper studies the dynamic average consensus problem of multi-agent systems under event-triggered communication. In this problem, each agent has access to a time-varying reference signal and aims to track the average of all reference signals. distributed algorithms with event-triggered communication have been developed to achieve dynamic average consensus. Nevertheless, these existing event-triggered communication mechanisms cannot guarantee the existence of a designable positive minimum inter-event time (MIET), which is important in their practical implementation. Motivated by this observation, we propose a distributed dynamic event-triggered communication mechanism (ETCM) for each agent. It is shown that the proposed ETCM guarantees the existence of a positive MIET that is locally adjustable by tuning design parameters. It is also shown that the dynamic average consensus is achieved with any pre-specified level of accuracy. As an illustrative example, the theoretical results are applied to a networked battery energy storage system for state-of-charge balancing and desired total power tracking.
This paper studies a clock synchronization problem for wireless sensor networks employing pulse-based communication when some of the nodes are faulty or even adversarial. The objective is to design resilient distribut...
详细信息
This paper studies a clock synchronization problem for wireless sensor networks employing pulse-based communication when some of the nodes are faulty or even adversarial. The objective is to design resilient distributed algorithms for the nonfaulty nodes to keep the influence of the malicious nodes minimal and to arrive at synchronization in a safe manner. Compared with conventional approaches, our algorithms are more capable in the sense that they are applicable to networks taking noncomplete graph structures. Our approach is to extend the class of mean subsequence reduced (MSR) algorithms from the area of multi-agent consensus. First, we provide a simple detection method to find malicious nodes that transmit pulses irregularly. Then, we demonstrate that in the presence of adversaries avoiding to be detected, the normal nodes can reach synchronization by ignoring suspicious pulses. Two extensions of this algorithm are further presented, which can operate under more adversarial attacks and also with relaxed conditions on the initial phases. We illustrate the effectiveness of our results by numerical examples.
作者：
Lei, JinlongYi, PengChen, JieHong, YiguangTongji Univ
Dept Control Sci & Engn Shanghai 201804 Peoples R China Tongji Univ
Shanghai Inst Intelligent Sci & Technol Shanghai 201804 Peoples R China Tongji Univ
Shanghai Res Inst Intelligent Autonomous Syst Shanghai 201804 Peoples R China Tongji Univ
Frontiers Sci Ctr Intelligent Autonomous Syst Shanghai 201804 Peoples R China
In this article, we consider distributed stochastic optimization over randomly switching networks, where agents collaboratively minimize the average of all agents' local expectation-valued convex cost functions. D...
详细信息
In this article, we consider distributed stochastic optimization over randomly switching networks, where agents collaboratively minimize the average of all agents' local expectation-valued convex cost functions. Due to the stochasticity in gradient observations, distributedness of local functions, and randomness of communication topologies, distributed algorithms with an exact convergence guarantee under fixed step-sizes have not been achieved yet. This work incorporates variance reduction scheme into the distributed stochastic gradient tracking algorithm, where local gradients are estimated by averaging across a variable number of sampled gradients. With an identically and independently distributed random network, we show that all agents' iterates converge almost surely to the same optimal solution under fixed step-sizes. When the global cost function is strongly convex and the sample size increases at a geometric rate, we prove that the iterates geometrically converge to the unique optimal solution, and establish the iteration, oracle, and communication complexity. The algorithm performance, including rate and complexity analysis, are further investigated with constant step-sizes and a polynomially increasing sample size. Finally, the empirical algorithm performance are illustrated with numerical examples.
暂无评论