Analysis of Max-Consensus Algorithms in Wireless Channels

Published on Nov 1, 2012in IEEE Transactions on Signal Processing5.028
· DOI :10.1109/TSP.2012.2211593
Franck Iutzeler13
Estimated H-index: 13
(ENST: Télécom ParisTech),
Philippe Ciblat30
Estimated H-index: 30
(ENST: Télécom ParisTech),
J. Jakubowicz2
Estimated H-index: 2
(Telecom SudParis)
Sources
Abstract
In this paper, we address the problem of estimating the maximal value over a sensor network using wireless links between them. We introduce two heuristic algorithms and analyze their theoretical performance. More precisely, i) we prove that their convergence time is finite with probability one, ii) we derive an upper-bound on their mean convergence time, and iii) we exhibit a bound on their convergence time dispersion.
📖 Papers frequently viewed together
9,402 Citations
20085.54Automatica
1 Author (Jorge Cortes, ..., Jorge Cortes)
377 Citations
2009
58 Citations
References27
Newest
Jan 17, 2012 in SODA (Symposium on Discrete Algorithms)
#1George Giakkoupis (U of C: University of Calgary)H-Index: 16
#2Thomas Sauerwald (MPG: Max Planck Society)H-Index: 23
We study the relation between the rate at which rumors spread throughout a graph and the vertex expansion of the graph. We consider the standard rumor spreading protocol where every node chooses a random neighbor in each round and the two nodes exchange the rumors they know. For any n-node graph with vertex expansion α, we show that this protocol spreads a rumor from a single node to all other nodes in [EQUATION] rounds with high probability. Further, we construct graphs for which Ω(α−1 log2 n) ...
57 CitationsSource
Jan 23, 2011 in SODA (Symposium on Discrete Algorithms)
#1Thomas Sauerwald (MPG: Max Planck Society)H-Index: 23
#2Alexandre Stauffer (University of California, Berkeley)H-Index: 13
We study the relation between the vertex expansion of a graph and the performance of randomized rumor spreading (push model). We prove that randomized rumor spreading takes O((1/α) · polylog(n)) time on any regular n-vertex graph with vertex expansion α. This bound extends previously known upper bounds by replacing conductance by vertex expansion. Our result is almost tight in the sense that the dependency on (1/α) is optimal (up to logarithmic factors) and that on non-regular graphs with consta...
41 CitationsSource
Mar 14, 2010 in INFOCOM (International Conference on Computer Communications)
#1Nikolaos Fountoulakis (MPG: Max Planck Society)H-Index: 19
#2Anna Huber (MPG: Max Planck Society)H-Index: 8
Last. Konstantinos Panagiotou (MPG: Max Planck Society)H-Index: 22
view all 3 authors...
Broadcasting algorithms are of fundamental importance for distributed systems engineering. In this paper we revisit the classical and well-studied push protocol for message broadcasting and we investigate a faulty version of it. Assuming that initially only one node has some piece of information, at each stage every one of the informed nodes chooses randomly and independently one of its neighbors and passes the message to it with some probability q that is, it fails to do so with probability 1-q...
54 CitationsSource
Jul 6, 2009 in ICALP (International Colloquium on Automata, Languages and Programming)
#1Benjamin Doerr (MPG: Max Planck Society)H-Index: 44
#2Tobias Friedrich (International Computer Science Institute)H-Index: 42
Last. Thomas Sauerwald (International Computer Science Institute)H-Index: 23
view all 3 authors...
Randomized rumor spreading is an efficient protocol to distribute information in networks. Recently, a quasirandom version has been proposed and proven to work equally well on many graphs and better for sparse random graphs. In this work we show three main results for the quasirandom rumor spreading model. We exhibit a natural expansion property for networks which suffices to make quasirandom rumor spreading inform all nodes of the network in logarithmic time with high probability. This expansio...
69 CitationsSource
#1T.C. Aysal (Cornell University)H-Index: 15
#2Mehmet E. Yildiz (Cornell University)H-Index: 13
Last. Anna Scaglione (UC Davis: University of California, Davis)H-Index: 58
view all 4 authors...
Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we study distributed broadcasting algorithms for exchanging information and computing in an arbitrarily connected network of nodes. Specifically, we study a broadcasting-based gossiping algorithm to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. We show that the broadcast gossip algorithm converges almost surely to a consensus. We prove that the random ...
415 CitationsSource
#1Chris GodsilH-Index: 40
#2Gordon F. RoyleH-Index: 23
Graphs.- Groups.- Transitive Graphs.- Arc-Transitive Graphs.- Generalized Polygons and Moore Graphs.- Homomorphisms.- Kneser Graphs.- Matrix Theory.- Interlacing.- Strongly Regular Graphs.- Two-Graphs.- Line Graphs and Eigenvalues.- The Laplacian of a Graph.- Cuts and Flows.- The Rank Polynomial.- Knots.- Knots and Eulerian Cycles.- Glossary of Symbols.- Index.
4,995 Citations
#1Alexandros G. Dimakis (University of California, Berkeley)H-Index: 57
#2Anand D. Sarwate (University of California, Berkeley)H-Index: 25
Last. Martin J. Wainwright (University of California, Berkeley)H-Index: 98
view all 3 authors...
Gossip algorithms for distributed computation are attractive due to their simplicity, distributed nature, and robustness in noisy and uncertain environments. However, using standard gossip algorithms can lead to a significant waste of energy by repeatedly recirculating redundant information. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is related to the slow mixing times of random walks on the communication graph. We pro...
171 CitationsSource
#1Jorge Cortes (UCSD: University of California, San Diego)H-Index: 50
#1Jorge E. Cortes (UCSD: University of California, San Diego)H-Index: 190
Last. Jorge Cortes (UCSD: University of California, San Diego)H-Index: 59
view all 1 authors...
This paper presents analysis and design results for distributed consensus algorithms in multi-agent networks. We consider continuous consensus functions of the initial state of the network agents. Under mild smoothness assumptions, we obtain necessary and sufficient conditions characterizing any algorithm that asymptotically achieves consensus. This characterization is the building block to obtain various design results for networks with weighted, directed interconnection topologies. We first id...
377 CitationsSource
Jun 26, 2006 in PODS (Symposium on Principles of Database Systems)
#1Srinivas Kashyap (UMD: University of Maryland, College Park)H-Index: 10
#2Supratim Deb (Bell Labs)H-Index: 20
Last. Anand Srinivasan (Bell Labs)H-Index: 18
view all 5 authors...
Recently, there has been a growing interest in gossip-based protocols that employ randomized communication to ensure robust information dissemination. In this paper, we present a novel gossip-based scheme using which all the nodes in an n-node overlay network can compute the common aggregates of MIN, MAX, SUM, AVERAGE, and RANK of their values using O(n log log n) messages within O(log n log log n) rounds of communication. To the best of our knowledge, ours is the first result that shows how to ...
57 CitationsSource
#1Stephen Boyd (Stanford University)H-Index: 152
#2Arpita Ghosh (Stanford University)H-Index: 7
Last. Devavrat Shah (MIT: Massachusetts Institute of Technology)H-Index: 66
view all 4 authors...
Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. The topology of such networks changes continuously as new nodes join and old nodes leave the network. Algorithms for such networks need to be robust against changes in topology. Additionally, nodes in sensor networks operate under limited computational, communication, an...
2,152 CitationsSource
Cited By89
Newest
#1Michelangelo BinH-Index: 8
#2Thomas ParisiniH-Index: 38
The paper deals with the distributed minimum sharing problem, in which a network of decision-makers - exchanging information through a communication network - computes the minimum of some local quantities of interest in a distributed and decentralized way. The problem is equivalently cast into a cost-coupled distributed optimization problem, and an adjustable approximate (or sub-optimal) solution is presented which enjoys several properties of crucial importance in applications. In particular, t...
Source
#2Jeffrey Hudack (AFRL: Air Force Research Laboratory)H-Index: 3
view all 3 authors...
Source
#1Yuanqiu Mo (Westlake University)
#2Lanlin Yu (Westlake University)
Last. Changbin Yu (UJ: University of Johannesburg)H-Index: 34
view all 3 authors...
Source
#1César A. Uribe (MIT: Massachusetts Institute of Technology)H-Index: 17
#2Soomin Lee (Yahoo!)H-Index: 12
Last. Angelia Nedic (ASU: Arizona State University)H-Index: 54
view all 4 authors...
We study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum ∑i=1mfi(z) of functions over in a network. We provide complexity ...
42 CitationsSource
We propose a privacy-preserving distributed maximum consensus algorithm where the local state of the agents and identity of the maximum state owner is kept private from adversaries. To that end, we reformulate the maximum consensus problem over a distributed network as a linear program. This optimization problem is solved in a distributed manner using the alternating direction method of multipliers (ADMM) and perturbing the primal update step with Gaussian noise. We define the privacy of an agen...
Source
#1Zilong Jiao (SU: Syracuse University)H-Index: 3
#2Jae C. Oh (SU: Syracuse University)H-Index: 9
Distributed exploration in multi-agent systems requires agents to retain a consistent view of the environment, even under limited communication ranges. We propose a consensus-based protocol for distributed exploration that enables agents to synchronize their local maps so that their collective global views are consistent. With the proposed protocol, agents can dynamically form communication networks and synchronize their local environment maps. In contrast to the existing consensus-based solutio...
Source
#1Diego Deplano (University of Cagliari)H-Index: 3
#2Mauro Franceschelli (University of Cagliari)H-Index: 16
Last. Alessandro Giua (University of Cagliari)H-Index: 53
view all 3 authors...
In this paper we propose a novel consensus protocol for discrete-time multi-agent systems (MAS), which solves the dynamic consensus problem on the max value, i.e., the dynamic max-consensus problem. In the dynamic max-consensus problem to each agent is fed a an exogenous reference signal, the objective of each agent is to estimate the instantaneous and time-varying value of the maximum among the signals fed to the network, by exploiting only local and anonymous interactions among the agents. The...
1 Citations
#1Hong Xing (SZU: Shenzhen University)H-Index: 15
#2Osvaldo Simeone ('KCL': King's College London)H-Index: 61
Last. Suzhi Bi (SZU: Shenzhen University)H-Index: 23
view all 3 authors...
Federated Learning (FL), an emerging paradigm for fast intelligent acquisition at the network edge, enables joint training of a machine learning model over distributed data sets and computing resources with limited disclosure of local data. Communication is a critical enabler of large-scale FL due to significant amount of model information exchanged among edge devices. In this paper, we consider a network of wireless devices sharing a common fading wireless channel for the deployment of FL. Each...
11 CitationsSource
#1Bhavana Singh (IITK: Indian Institute of Technology Kanpur)H-Index: 1
#2Arijit Sen (IITK: Indian Institute of Technology Kanpur)H-Index: 6
Last. Soumya Ranjan Sahoo (IITK: Indian Institute of Technology Kanpur)H-Index: 9
view all 3 authors...
For a multi-agent system (MAS), researchers have explored min-consensus for single-integrators under uniformly strongly-connected digraph, and double-integrators under jointly-connected graphs. However, the extension of these works is non-trivial for heterogeneous higher-order integrators under switching digraphs. This paper proposes a min-consensus protocol for MAS with higher-order integrators under uniformly strongly-connected digraph. The protocol consists of a distributed observer and a dec...
2 CitationsSource
#1Gowtham Muniraju (ASU: Arizona State University)H-Index: 6
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 28
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 32
view all 3 authors...
A consensus based distributed algorithm to compute the spectral radius of a network is proposed. The spectral radius of the graph is the largest eigenvalue of the adjacency matrix, and is a useful characterization of the network graph. Conventionally, centralized methods are used to compute the spectral radius, which involves eigenvalue decomposition of the adjacency matrix of the underlying graph. Our distributed algorithm uses a simple update rule to reach consensus on the spectral radius, usi...
3 CitationsSource