Publication

Revisiting the Relationship between Non-Blocking Atomic Commitment and Consensus

Rachid Guerraoui
1995
Conference Papers

Résumé

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.

Source officielle

https://infoscience.epfl.ch/entities/publication/6c8b7d19-ce3d-45bf-9b65-6486eed0017c

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Rachid Guerraoui
1995
Conference Papers

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/6c8b7d19-ce3d-45bf-9b65-6486eed0017c

À propos de ce résultat

Concepts associés (14)

Commitment ordering

Commitment ordering (CO) is a class of interoperable serializability techniques in concurrency control of databases, transaction processing, and related applications. It allows optimistic (non-blocking) implementations. With the proliferation of multi-core processors, CO has also been increasingly utilized in concurrent programming, transactional memory, and software transactional memory (STM) to achieve serializability optimistically. CO is also the name of the resulting transaction schedule (history) property, defined in 1988 with the name dynamic atomicity.

Two-phase commit protocol

In transaction processing, databases, and computer networking, the two-phase commit protocol (2PC, tupac) is a type of atomic commitment protocol (ACP). It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort (roll back) the transaction. This protocol (a specialised type of consensus protocol) achieves its goal even in many cases of temporary system failure (involving either process, network node, communication, etc.

Dissuasion et prolifération nucléaires au XXIe siècle

La dissuasion et la prolifération nucléaires au sont une dimension clé des politiques de sécurité nationale des États qui possèdent l'arme nucléaire ou développent un programme nucléaire, et occupent une place centrale dans les négociations multilatérales relatives à la non-prolifération et au désarmement nucléaires qui sont conduites dans le cadre de l'ONU, de l'Agence internationale de l'énergie atomique, du traité sur la non-prolifération et des relations entre les grandes puissances.

Afficher plus