On the Influence of Noise in Randomized Consensus Algorithms
In this paper we study the influence of additive noise in randomized consensus algorithms. Assuming that the update matrices are symmetric, we derive a closed form expression for the mean square error induced by the noise, together with upper and lower bounds that are simpler to evaluate. Motivated by the study of Open Multi-Agent Systems, we concentrate on Randomly Induced Discretized Laplacians, a family of update matrices that are generated by sampling subgraphs of a large undirected graph. For these matrices, we express the bounds by using the eigenvalues of the Laplacian matrix of the underlying graph or the graph's average effective resistance, thereby proving their tightness. Finally, we derive expressions for the bounds on some examples of graphs and numerically evaluate them.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols
In this work we present a new framework for the analysis and design of randomized gossip algorithms for solving the average consensus problem. We show how classical randomized iterative methods for solving linear systems…
Randomized Matrix Weighted Consensus
In this paper, randomized gossip-type matrix-weighted consensus algorithms are proposed for both leaderless and leader-follower topologies. First, we introduce the notion of expected matrix-weighted network, which captur…
Deterministic Approximate Methods for Maximum Consensus Robust Fitting
Maximum consensus estimation plays a critically important role in robust fitting problems in computer vision. Currently, the most prevalent algorithms for consensus maximization draw from the class of randomized hypothes…
A Privacy Preserving Randomized Gossip Algorithm via Controlled Noise Insertion
In this work we present a randomized gossip algorithm for solving the average consensus problem while at the same time protecting the information about the initial private values stored at the nodes. We give iteration co…
Privacy PreservingEnhancing Robustness of LLM-Driven Multi-Agent Systems through Randomized Smoothing
This paper presents a defense framework for enhancing the safety of large language model (LLM) empowered multi-agent systems (MAS) in safety-critical domains such as aerospace. We apply randomized smoothing, a statistica…
Computational Efficiency