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. Revisiting the Relationship between Non-Blocking Atomic Commitment and Consensus
 
conference paper

Revisiting the Relationship between Non-Blocking Atomic Commitment and Consensus

Guerraoui, R.  
1995
Distributed Algorithms. WDAG 1995
9th International Workshop on Distributed Algorithms (WDAG-9)

This paper discusses the relationship between the {\em Non-\Blocking Atomic Commitment problem (NB-AC)} and the Consensus problem in asynchronous systems with unreliable failure detectors. We first confirm that NB-AC is harder than Consensus. In contrast to Consensus, NB-AC is impossible to solve with unreliable failure detectors even with a single crash failure. We define a weaker problem than NB-AC, called Non-Blocking Weak Atomic Commitment (NB-WAC), which is sufficient to solve for most practical situations. A fundamental characteristic of NB-WAC is its {\em reducibility} to Consensus. The previous results on solving Consensus with unreliable failure detectors apply therefore to NB-WAC. An interesting intermediate result of this reducibility is that Uniform Consensus and Consensus are equivalent problems. We show actually that any algorithm that solves Consensus with unreliable failure detectors also solves Uniform Consensus.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

Gue95.ps

Access type

openaccess

Size

173.42 KB

Format

Postscript

Checksum (MD5)

e953acba51615813e4c396ab6f2c14b0

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