检索结果-内蒙古大学图书馆

Notes on Linear gossip algorithms:Potentials and Challenges

Journal of Systems Science & Complexity 2025年第1期38卷 98-128页

作者： GERENCSER Balazs GERENCSER Laszlo HUN-REN Alfred Renyi Institute of Mathematics Budapest 1052Hungary and Eotvos Lorand UniversityDepartment of Probability and StatisticsBudapest 1518Hungary HUN-REN SZTAKI Institute for Computer Science and ControlBudapest 1111Hungary

The authors consider the problem of reaching consensus over a communication network via asynchronous interaction between pairs of agents.A well-known method is the linear gossip algorithm due to Tsitsiklis(1984).Extension of this,allowing the selection of a strictly stationary sequence of communicating pairs,was given in Picci and Taylor(2013).Extension of the linear gossip algorithm to directed communication networks,retaining the linear dynamics,was proposed by Cai and Ishii(2012),later extended by Silvestre,et al.(2018).A definite novelty of these algorithms is that L2-convergence with exponential rate can be *** authors attend the above issues,extending the result of Picci and Taylor(2013)motivated by features of algorithms for directed *** authors present and discuss the algorithm of Silvestre,et al.(2018),together with systematic simulation results based on 5M randomly chosen parameter *** core of the proposed mathematical technology is a set of simple observations,presented with a tutorial aspect,by which the authors can conveniently establish various results on the almost sure convergence of products of strictly stationary sequences of matrices to a rank-1 matrix.

关键词： Consensus gossip algorithms Lyapunov-exponents spectral gap

来源：评论

学校读者我要写书评

暂无评论

gossip algorithms for Convex Consensus Optimization Over Networks

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2011年第12期56卷 2911-2918页

作者： Lu, Jie Tang, Choon Yik Regier, Paul R. Bow, Travis D. Univ Oklahoma Sch Elect & Comp Engn Norman OK 73019 USA Stanford Univ Dept Mech Engn Stanford CA 94305 USA

In many applications, nodes in a network desire not only a consensus, but an optimal one. To date, a family of subgradient algorithms have been proposed to solve this problem under general convexity assumptions. This technical note shows that, for the scalar case and by assuming a bit more, novel non-gradient-based algorithms with appealing features can be constructed. Specifically, we develop Pairwise Equalizing (PE) and Pairwise Bisectioning (PB), two gossip algorithms that solve unconstrained, separable, convex consensus optimization problems over undirected networks with time-varying topologies, where each local function is strictly convex, continuously differentiable, and has a minimizer. We show that PE and PB are easy to implement, bypass limitations of the subgradient algorithms, and produce switched, nonlinear, networked dynamical systems that admit a common Lyapunov function and asymptotically converge. Moreover, PE generalizes the well-known Pairwise Averaging and Randomized gossip Algorithm, while PB relaxes a requirement of PE, allowing nodes to never share their local functions.

关键词： Distributed consensus distributed convex optimization gossip algorithms networked dynamical systems

来源：评论

学校读者我要写书评

暂无评论

gossip algorithms for Decentralized Congestion Management of Distribution Grids

引用

IEEE TRANSACTIONS ON SUSTAINABLE ENERGY 2016年第3期7卷 1071-1080页

作者： Koukoula, Despina I. Hatziargyriou, Nikos D. Natl Tech Univ Athens Dept Elect Engn Power Syst Lab Athens 15780 Greece

The paper proposes a gossip algorithm-based architecture for managing power flows on radial distribution grids applying decentralized management of demand. Demand flexibility is associated with a cost-like utility function expressing the inconvenience caused by curtailment. Every node of the distribution grid participates in power flow management by sending locally measured and calculated values to its neighboring nodes following a peer-to-peer architecture. The proposed algorithm is based on the application of gossip algorithms to estimate locally critical physical quantities by reaching a global consensus. More specifically, the solution implements gossip algorithms to achieve consensus in aggregated demand and in minimum cost for curtailment of flexible loads/increase of controllable distributed generators.

关键词： Smart Girds Distributed algorithms gossip algorithms Distribution Grids Power Flow Management Demand Flexibility Distribution Management System

来源：评论

学校读者我要写书评

暂无评论

gossip algorithms for heterogeneous multi-vehicle routing problems

引用

NONLINEAR ANALYSIS-HYBRID SYSTEMS 2013年第1期10卷 156-174页

作者： Franceschelli, Mauro Rosa, Daniele Seatzu, Carla Bullo, Francesco Univ Cagliari Dept Elect & Elect Engn I-09124 Cagliari Italy Univ Calif Santa Barbara Dept Mech Engn Santa Barbara CA 93106 USA

In this paper we address a class of heterogeneous multi-vehicle task assignment and routing problems. We propose two distributed algorithms based on gossip communication: the first algorithm is based on a local exact optimization and the second is based on a local approximate greedy heuristic. We consider the case where a set of heterogeneous tasks arbitrarily distributed in a plane has to be serviced by a set of mobile robots, each with a given movement speed and task execution speed. Our goal is to minimize the maximum execution time of robots. (c) 2013 Elsevier Ltd. All rights reserved.

关键词： gossip algorithms Distributed optimization Multi-TSP Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

gossip algorithms for Average Energy Estimation in Wireless Sensor Networks

Gossip Algorithms for Average Energy Estimation in Wireless ...

引用

3rd International Conference on Mechanical, Control, and Electronic Information (ICMCEI)

作者： Wang, Yuze Wu, Shaochuan Cui, Wen Harbin Inst Technol Sch Elect & Informat Engn Harbin 150001 Heilongjiang Peoples R China

ISBN: (纸本)9783038351559

gossip algorithms which belong to a kind of distributed algorithms can be used to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. This paper proposes an improved broadcast gossip algorithm to estimate average energy with better accuracy. In this proposed algorithm, we use some companion variables to save the sum, and convergence error is decreasing with the number of companion variables increasing. Convergence of the proposed algorithm is studied theoretically and verified by simulations. Although the estimated value is random, we show that the novel algorithm can converge closer to average than broadcast gossip algorithm in probability.

关键词： Distributed averaging gossip algorithms broadcast sensor networks

来源：评论

学校读者我要写书评

暂无评论

Randomized gossip algorithms for maintaining a distributed bulletin board with guaranteed age properties

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2009年第15期21卷 1907-1927页

作者： Amar, Lior Barak, Amnon Drezner, Zvi Okun, Michael Hebrew Univ Jerusalem Dept Comp Sci IL-91904 Jerusalem Israel Calif State Univ Fullerton Coll Business & Econ Fullerton CA 92834 USA Weizmann Inst Sci Dept Neurobiol IL-76100 Rehovot Israel

Scalable computer systems, including clusters and multi-cluster grids, require routine exchange of information about the state of system-wide resources among their nodes. gossip-based algorithms are popular for providing such information services due to their simplicity, fault tolerance and low communication overhead. This paper presents a randomized gossip algorithm for maintaining a distributed bulletin board among the nodes of a scalable computer system. In this algorithm each node routinely disseminates its most recently acquired information while maintaining a snapshot of the other nodes' states. The paper provides analytical approximations for the expected average age, the age distribution and the expected maximal age for the acquired information at each node. We confirm our results by measurements of the performance of the algorithm on a multi-cluster campus grid with 256 nodes and by simulations of configurations with up to 2048 nodes. The paper then presents practical enhancements of the algorithm, which makes it more suitable for a real system. Such enhancements include using fixed-size messages, reducing the number of messages sent to inactive nodes and supporting urgent information. The enhanced algorithm guarantees the age properties of the information at each node in the configurations with an arbitrary number of inactive nodes. It is being used in our campus grid for resource discovery, for dynamic assignment of processes to the best available nodes, for load-balancing and for on-line monitoring. Copyright (C) 2009 John Wiley & Sons, Ltd.

关键词： distributed bulletin board gossip algorithms information dissemination grid and cluster management systems resource discovery rumor spreading

来源：评论

学校读者我要写书评

暂无评论

Distributed Averaging in Sensor Networks Based on Broadcast gossip algorithms

引用

IEEE SENSORS JOURNAL 2011年第3期11卷 808-817页

作者： Franceschelli, Mauro Giua, Alessandro Seatzu, Carla Univ Cagliari Dept Elect & Elect Engn I-09123 Cagliari Italy

In this paper, we propose a new decentralized algorithm to solve the consensus on the average problem on sensor networks through a gossip algorithm based on broadcasts. We directly extend previous results by not requiring that the digraph representing the network topology be balanced. Our algorithm is an improvement with respect to known gossip algorithms based on broadcasts in that the average of the initial state is preserved after each broadcast. The nodes are assumed to know their out-degree anytime they transmit information.

关键词： Consensus distributed averaging gossip algorithms sensor networks

来源：评论

学校读者我要写书评

暂无评论

Resilient gossip algorithms for collecting online management information in exascale clusters

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2015年第17期27卷 4797-4818页

作者： Barak, Amnon Drezner, Zvi Levy, Ely Lieber, Matthias Shiloh, Amnon Hebrew Univ Jerusalem Dept Comp Sci IL-91904 Jerusalem Israel Calif State Univ Fullerton Coll Business & Econ Fullerton CA 92834 USA Tech Univ Dresden Ctr Informat Serv & High Performance Comp D-01062 Dresden Germany

Management of forthcoming exascale clusters requires frequent collection of run-time information about the nodes and the running applications. This paper presents a new paradigm for providing online information to the management system of scalable clusters, consisting of a large number of nodes and one or more masters that manage these nodes. We describe the details of resilient gossip algorithms for sharing local information within subsets of nodes and for sending global information to a master, which holds information on all the nodes. The presented algorithms are decentralized, scalable and resilient, working well even when some nodes fail, without needing any recovery protocol. The paper gives formal expressions for approximating the average ages of the local information at each node and the information collected by the master. It then shows that these results closely match the results of simulations and measurements on a real cluster. The paper also investigates the resilience of the algorithms and the impact on the average age when nodes or masters fail. The main outcome of this paper is that partitioning of large clusters can improve the quality of information available to the management system without increasing the number of messages per node. Copyright (c) 2015 John Wiley & Sons, Ltd.

关键词： exascale clusters gossip algorithms resource management

来源：评论

学校读者我要写书评

暂无评论

Convergence Rate Analysis of Periodic gossip algorithms for One-Dimensional Lattice WSNs

引用

IEEE SENSORS JOURNAL 2020年第21期20卷 13150-13160页

作者： Kouachi, Said Dhuli, Sateeshkrishna Singh, Yatindra Nath Qassim Univ Dept Math Buraydah 51452 Saudi Arabia SRM Univ AP Amaravati Elect & Commun Engn Dept Mangalagiri 522502 India IIT Kanpur Dept Elect Engn Kanpur 208016 Uttar Pradesh India

gossip algorithms have received a lot of attention in recent years due to their ability to compute global statistics using local pair-wise communications. Simple execution, robustness to topology changes, and distributed nature make these algorithms more attractive to wireless sensor network (WSN) applications. Periodic gossip algorithm is a special case of gossip algorithm, where neighbouring nodes gossip at every time instant. Convergence rate plays a fundamental role in effectively measuring the performance of periodic gossip algorithms. However, these algorithms are inherently iterative and estimating their convergence rate for large-scale WSNs is a computationally challenging task. Hence, to utilize the periodic gossip algorithms for sensor networks, it is necessary to study the convergence rate with less computational resources. In this work, we model the WSN as a one-dimensional lattice network and derive the closed form expressions of convergence rate for even and odd number of nodes. To realize the closed-form expressions of convergence rate, we obtain the exact formulas of eigenvalues for pentadiagonal matrices. The numerical analysis reveals the new design insights into the effect of gossip weight, network size, and probability of link failures on the performance of convergence rate. Specifically, we prove that w = 0.9 achieves fast convergence rate over w =0.5 for large-scale WSNs. Our theoretical results provide the basic analytical tools for controlling the performance of periodic gossip algorithms in large-scale WSNs.

关键词： gossip algorithms wireless sensor networks eigenvalues of pentadiagonal matrices lattice networks convergence rate periodic gossip algorithms

来源：评论

学校读者我要写书评

暂无评论

Acceleration of gossip algorithms through the Euler-Poisson-Darboux Equation

引用

IMA JOURNAL OF APPLIED MATHEMATICS 2022年第6期87卷 985-1009页

作者： Berthier, Raphael Li, Mufan (Bill) Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland Univ Toronto Toronto ON M5G 1Z5 Canada Vector Inst Toronto ON M5G 1Z5 Canada

gossip algorithms and their accelerated versions have been studied exclusively in discrete time on graphs. In this work, we take a different approach and consider the scaling limit of gossip algorithms in both large graphs and large number of iterations. These limits lead to well-known partial differential equations (PDEs) with insightful properties. On lattices, we prove that the non-accelerated gossip algorithm of converges to the heat equation, and the accelerated Jacobi polynomial iteration of converges to the Euler-Poisson-Darboux (EPD) equation-a damped wave equation. Remarkably, with appropriate parameters, the fundamental solution of the EPD equation has the ideal gossip behaviour: a uniform density over an ellipsoid, whose radius increases at a rate proportional to $t$-the fastest possible rate for locally communicating gossip algorithms. This is in contrast with the heat equation where the density spreads on a typical scale of root t. Additionally, we provide simulations demonstrating that the gossip algorithms are accurately approximated by their limiting PDEs.

关键词： gossip algorithms Euler-Poisson-Darboux equation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：