Convergence speed of binary interval consensus

DOI10.1137/110823018MaRDI QIDQ2910896zbMATH OpenOpenAlexFDO

Authors Moez Draief, Vojnović Milan

Publication date 12 September 2012

Published in SIAM Journal on Control and Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.1083

zbMATH Keywords

binary interval consensusexpected convergence timevoting margin

Mathematics Subject Classification ID

Applications of graph theory (05C90) Deterministic network models in operations research (90B10) Random dynamical systems (37H99)

Abstract: We consider the convergence time for solving the binary consensus problem using the interval consensus algorithm proposed by B' en' ezit, Thiran and Vetterli (2009). In the binary consensus problem, each node initially holds one of two states and the goal for each node is to correctly decide which one of these two states was initially held by a majority of nodes. We derive an upper bound on the expected convergence time that holds for arbitrary connected graphs, which is based on the location of eigenvalues of some contact rate matrices. We instantiate our bound for particular networks of interest, including complete graphs, paths, cycles, star-shaped networks, and Erd" os-R' enyi random graphs; for these graphs, we compare our bound with alternative computations. We find that for all these examples our bound is tight, yielding the exact order with respect to the number of nodes. We pinpoint the fact that the expected convergence time critically depends on the voting margin defined as the difference between the fraction of nodes that initially held the majority and the minority states, respectively. The characterization of the expected convergence time yields exact relation between the expected convergence time and the voting margin, for some of these graphs, which reveals how the expected convergence time goes to infinity as the voting margin approaches zero. Our results provide insights into how the expected convergence time depends on the network topology which can be used for performance evaluation and network design. The results are of interest in the context of networked systems, in particular, peer-to-peer networks, sensor networks and distributed databases.

Recommendations

• Convergence speed in distributed consensus and averaging
• Convergence speed in distributed consensus and averaging
• Interval consensus over random networks
• Convergence time analysis of quantized gossip consensus on digraphs
• Convergence in (social) influence networks

Cited in

(15)

• Noisy rumor spreading and plurality consensus
• Majority consensus thresholds in competitive Lotka-Volterra populations
• Game dynamics and equilibrium computation in the population protocol model
• Approximate majority analyses using tri-molecular chemical reaction networks
• Polylogarithmic-time leader election in population protocols
• scientific article; zbMATH DE number 7651155 (Why is no real title available?)
• Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions
• Simple dynamics for plurality consensus
• Probabilistic consensus via polling and majority rules
• Fixed-time connectivity preserving tracking consensus of multiagent systems with disturbances
• Brief Announcement: Population Protocols Decide Double-exponential Thresholds
• Automatic analysis of expected termination time for population protocols
• Determining majority in networks with local interactions and very small local memory
• Time-space trade-offs in population protocols for the majority problem
• A tight analysis of the parallel undecided-state dynamics with two colors

This page was built for publication: Convergence speed of binary interval consensus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910896)