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) Random dynamical systems (37H99) Deterministic network models in operations research (90B10)

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.

Review text

Algorithms for distributed computation attract interest because of applications in peer-to-peer, sensor, online social networks and distributed databases. A problem of interest is the so-called binary consensus where, initially, each node of the network holds one of two states and the goal is to decide which of two states was initially held by the majority of nodes. This is done by a decentralized algorithm where changes are based on the information exchanged at contacts with other nodes restricted by the network topology. The paper focusses on binary interval consensus to find which of two partitions contains the average of the initial values held by the individual nodes, for this case it answers the question how fast the interval consensus converges to the final state. An upper bound of expected convergence time is found on arbitrary connected graphs. The method is demonstrated for complete graphs, paths, cycles and Erdős-Rényi graphs. The results show how the expected convergence time depends on the network structure and the voting margin defined as the difference between the fraction of nodes initially holding the majority state and the fraction of nodes initially holding the minority state.

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)

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

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)