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. Journal articles
  4. The gap in circumventing the impossibility of consensus
 
research article

The gap in circumventing the impossibility of consensus

Guerraoui, Rachid  
•
Kuznetsov, Petr
2008
Journal of Computer and System Sciences

The impossibility of reaching deterministic consensus in an asynchronous and crash prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value in {0, 1}, so that both 0 and 1 are possible decision values. On the other hand, approaches to circumventing the impossibility focused on a stronger variant of the problem, called consensus, where the processes need to decide on one of the values they initially propose (0 or 1). This paper studies the computational gap between the two problems. We show that any set of deterministic object types that, combined with registers, implements weak consensus, also implements consensus. Then we exhibit a non-deterministic type that implements weak consensus, among any number of processes, but, combined with registers, cannot implement consensus even among two processes. In modern terminology, this type has consensus power 1 and weak consensus power infinity.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1016/j.jcss.2007.10.002
Web of Science ID

WOS:000256462000010

Author(s)
Guerraoui, Rachid  
Kuznetsov, Petr
Date Issued

2008

Published in
Journal of Computer and System Sciences
Volume

74

Start page

823

End page

830

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Available on Infoscience
May 23, 2008
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/25910
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