Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Using Three States for Binary Consensus on Complete Graphs
 
conference paper

Using Three States for Binary Consensus on Complete Graphs

Perron, Etienne
•
Vasudevan, Dinkar
•
Vojnovic, Milan
2009
Ieee Infocom 2009 - Ieee Conference On Computer Communications
IEEE INFOCOM Conference 2009

We consider the binary consensus problem where each node in the network initially observes one of two states and the goal for each node is to eventually decide which one of the two states was initially held by the majority of the nodes. Each node contacts other nodes and updates its current state based on the state communicated by the last contacted node. We assume that both signaling (the information exchanged at node contacts) and memory (computation state at each node) are limited and restrict our attention to systems where each node can contact any other node (i.e., complete graphs). It is well known that for systems with binary signaling and memory, the probability of reaching incorrect consensus is equal to the fraction of nodes that initially held the minority state. We show that extending both the signaling and memory by just one state dramatically improves the reliability and speed of reaching the correct consensus. Specifically, we show that the probability of error decays exponentially with the number of nodes N and the convergence time is logarithmic in N for large N. We also examine the case when the state is ternary and signaling is binary. The convergence of this system to consensus is again shown to be logarithmic in N for large N, and is therefore faster than purely binary systems. The type of distributed consensus problems that we study arises in the context of decentralized peer-to-peer networks, e.g. sensor networks and opinion formation in social networks - our results suggest that robust and efficient protocols can be built with rather limited signaling and memory.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/INFCOM.2009.5062181
Web of Science ID

WOS:000275366201081

Author(s)
Perron, Etienne
•
Vasudevan, Dinkar
•
Vojnovic, Milan
Date Issued

2009

Publisher

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa

Published in
Ieee Infocom 2009 - Ieee Conference On Computer Communications
ISBN of the book

978-1-4244-3512-8

Start page

2527

End page

2535

Subjects

Distributed Detection

•

Multiple Sensors

Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LICOS  
Event nameEvent placeEvent date
IEEE INFOCOM Conference 2009

Rio de Janeiro, BRAZIL

Apr 19-25, 2009

Available on Infoscience
November 30, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/59437
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés