Designing privacy-preserving distributed algorithms for stochastic aggregative games is urgent due to the privacy issues caused by information exchange between players. This paper proposes two differentially private d...
详细信息
Designing privacy-preserving distributed algorithms for stochastic aggregative games is urgent due to the privacy issues caused by information exchange between players. This paper proposes two differentially private distributed algorithms seeking the Nash equilibrium in stochastic aggregative games. By adding time-varying random noises, the input and output-perturbation methods are given to protect each player's sensitive information. For the case of output-perturbation, utilizing mini-batch methods, the algorithm's mean square error is inversely proportional to the privacy level E and the number of samples. For the case of input-perturbation, a differentially private distributed stochastic approximation-type algorithm is developed to achieve almost sure convergence and (epsilon, delta)-differential privacy. Under suitable consensus time conditions, the algorithm's convergence rate is rigorously presented for the first time, where the optimal convergence rate O(1/k) in a mean square sense is obtained. Then, utilizing mini-batch methods, the influence of added privacy noise on the algorithm's performance is reduced, and the convergence rate of the algorithm is improved. Specifically, when the batch sizes and the number of consensus times at each iteration grow at a suitable rate, an exponential rate of convergence can be achieved with the same privacy level. Finally, a simulation example demonstrates the algorithms' effectiveness. (C) 2022 Elsevier Ltd. All rights reserved.
Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of intere...
详细信息
ISBN:
(纸本)9781450380539
Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two questions: (i) What network topology parameters determine the complexity of distributed optimization? (ii) Are there universally-optimal algorithms that are as fast as possible on every topology? We resolve these 25-year-old open problems in the known-topology setting (i.e., supported CONGEST) for a wide class of global network optimization problems including MST, (1+epsilon)-min cut, various approximate shortest paths problems, sub-graph connectivity, etc. In particular, we provide several (equivalent) graph parameters and show they are tight universal lower bounds for the above problems, fully characterizing their inherent complexity. Our results also imply that algorithms based on the low-congestion shortcut framework match the above lower bound, making them universally optimal if shortcuts are efficiently approximable.
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the f...
详细信息
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is (f + epsilon). Let Delta denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requires O(log Delta/ log log Delta) rounds, for constants epsilon is an element of (0, 1] and f is an element of N+. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and e, our algorithm improves over the (f + epsilon)-approximation algorithm of Kuhn et al. (SODA, 2006)whose running time is O(log. + logW), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f -approximation for the problem in O(f log n) rounds, improving over the classical result of Khuller et al. (J algorithms, 1994) that achieves a running time of O(f log(2) n). Finally, for weighted vertex cover (f = 2) our algorithm achieves a deterministic running time of O(log n), matching the randomized previously best result of Koufogiannakis and Young (Distrib Comput, 2011). We also show that integer covering-programs can be reduced to the MinimumWeight Set Cover problem in the distributed setting. This allows us to achieve an (f inverted right perpendicularlog(2)(M)+1inverted left perpendicular+ epsilon)-approximate integral solution in O ((1 + f / log n) . (log Delta/log log Delta + (f . log M)(1.01) . log epsilon(-1) . (log Delta)(0.01))) rounds, where f bounds the number of variables in a constraint, Delta bounds the number of constraints a variable appears in, and M = max {1, inverted left perpendicular1/a(min) inverted
Consider a wireless network where each communication link has a minimum bandwidth quality-of-service requirement. Certain pairs of wireless links interfere with each other due to being in the same vicinity, and this i...
详细信息
Consider a wireless network where each communication link has a minimum bandwidth quality-of-service requirement. Certain pairs of wireless links interfere with each other due to being in the same vicinity, and this interference is modeled by a conflict graph. Given the conflict graph and link bandwidth requirements, the objective is to determine, using only localized information, whether the demands of all the links can be satisfied. At one extreme, each node knows the demands of only its neighbors;at the other extreme, there exists an optimal, centralized scheduler that has global information. The present work interpolates between these two extremes by quantifying the tradeoff between the degree of decentralization and the performance of the distributed algorithm. This open problem is resolved for the primary interference model, and the following general result is obtained: if each node knows the demands of all links in a ball of radius $d$ centered at the node, then there is a distributed algorithm whose performance is away from that of an optimal, centralized algorithm by a factor of at most ${{ (2d+3)}}/{{ (2d+2)}}$ . The tradeoff between performance and complexity of the distributed algorithm is also analyzed. It is shown that for line networks under the protocol interference model, the row constraints are a factor of at most 3 away from optimal. Both bounds are best possible.
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...
详细信息
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 perform community detection, a computational problem which is nontrivial even in a centralized setting.
This paper studies the distributed algorithms to obtain a solution of the linear equation Ax = b in finite time (FT) over a multi-agent network. In order to guarantee the settling time without depending on the initial...
详细信息
This paper studies the distributed algorithms to obtain a solution of the linear equation Ax = b in finite time (FT) over a multi-agent network. In order to guarantee the settling time without depending on the initial states, the fixed-time (FxT) distributed algorithms are also provided to obtain a solution within a globally bounded time. Specifically, three distributed nonlinear algorithms are developed. The first one is designed to achieve FT/FxT consensus on a solution with special initialization. The second is to obtain the solution in FT/FxT with free initialization by first driving the local states to satisfy the special initialization in FT/FxT time. The last one is to guarantee the FT/FxT convergence to a solution closest to specific points when multiple solutions exist. Finally, three case studies are performed to show the effectiveness of the proposed algorithms. (C) 2019 Elsevier Ltd. All rights reserved.
This paper investigates asynchronous algorithms for distributedly seeking generalized Nash equilibria with delayed information in multiagent networks. In the game model, a shared affine constraint couples all players&...
详细信息
This paper investigates asynchronous algorithms for distributedly seeking generalized Nash equilibria with delayed information in multiagent networks. In the game model, a shared affine constraint couples all players' local decisions. Each player is assumed to only access its private objective function, private feasible set, and a local block matrix of the affine constraint. We first give an algorithm for the case when each agent is able to fully access all other players' decisions. By using auxiliary variables related to communication links and the edge Laplacian matrix, each player can carry on its iteration asynchronously with only private data and possibly delayed information from its neighbors. Then, we consider the case when agents cannot know all other players' decisions, called a partial-decision information case. We introduce a local estimation of the overall agents' decisions and incorporate consensus dynamics on these local estimations. The two algorithms do not need any centralized clock coordination, fully exploit the local computation resource, and remove the idle time due to waiting for the "slowest" agent. Both algorithms are developed by preconditioned forward-backward operator splitting, and their convergence is shown by relating them to asynchronous fixed-point iterations, under proper assumptions and fixed and nondiminishing step-size choices. Numerical studies verify the algorithms' convergence and efficiency.
This paper considers the problem of distributively verifying and ensuring strong connectivity of directed networks. Strong connectivity of a directed graph associated with the communication network topology is crucial...
详细信息
ISBN:
(纸本)9781665436601
This paper considers the problem of distributively verifying and ensuring strong connectivity of directed networks. Strong connectivity of a directed graph associated with the communication network topology is crucial in ensuring the convergence of many distributed algorithms. Specifically, inspired by maximum consensus algorithm, we first propose a distributed algorithm that enables nodes in a networked system to verify strong connectivity of a directed graph. Then, given an arbitrary weakly connected directed graph, we develop a distributed algorithm to augment additional links to ensure the directed graph’s strong connectivity. Both algorithms are implemented without requiring information of the overall network topology and are scalable (linearly with the number of nodes) as they only require finite storage and converge in finite number of steps. Finally, the proposed distributed algorithms are demonstrated via several examples.
The recovery of missing samples from available noisy measurements is a fundamental problem in signal processing. This process is also sometimes known as graph signal inpainting, reconstruction, forecasting or inferenc...
详细信息
The recovery of missing samples from available noisy measurements is a fundamental problem in signal processing. This process is also sometimes known as graph signal inpainting, reconstruction, forecasting or inference. Many of the existing algorithms do not scale well with the size of the graph and/or they cannot be implemented efficiently in a distributed manner. In this paper, we develop efficient distributed algorithms for the recovery of time-varying graph signals. The a priori assumptions are that the signal is smooth with respect to the graph topology and correlative across time. These assumptions can be incorporated in an optimization formulation of the algorithm via Tikhonov regularization terms. Our formulation is tailored to yield algorithms that can be efficiently implemented in a distributed manner. Two different distributed algorithms, arising from two different formulations, are proposed to solve the optimization problems. The first involves the l(2)-norm, and a distributed least squared recovery algorithm (DLSRA) is proposed that leverages the graph topology and sparsity of the corresponding Hessian matrix. Updates of the Hessian inverse are not required here. The second involves the l(1)-norm and the philosophy of the alternating direction method of multipliers (ADMM) is utilized to develop the algorithm. An inexact Newton method is incorporated into the conventional ADMM to give a distributed ADMM recovery algorithm (DAMRA). The two distributed algorithms require only data exchanges between vertices in localized neighbourhood subgraphs. Experiments on a variety of synthetic and real-world datasets demonstrate that the proposed algorithms are superior to the existing methods in terms of the computational complexity and convergence rate.
Proving the correctness of distributed algorithms is a difficult challenge in dynamic networks. In these networks, topological changes can take place due to unexpected appearance and disappearance of devices and commu...
详细信息
Proving the correctness of distributed algorithms is a difficult challenge in dynamic networks. In these networks, topological changes can take place due to unexpected appearance and disappearance of devices and communication links. The existing studies in the literature lack a general model for their development and their proof. Besides, most of the proofs which have been introduced are handwritten. Our work aims at providing a reusable approach which reduces the specification and verification efforts of distributed algorithms. At the first stage, we present a basic pattern which aims to deal with topological events. At the second stage, we extend this pattern to construct and maintain a spanning forest in a dynamic network. We illustrate the extended pattern through the leader election algorithm. We show the efficiency of our approach by presenting the number of proofs associated with the development of the algorithm with and without using the pattern. (C) 2020 Elsevier B.V. All rights reserved.
暂无评论