Publication

Revisiting the Relationship between Non-Blocking Atomic Commitment and Consensus

Rachid Guerraoui
1995
Conference Papers

Abstract

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.

Official source

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

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Rachid Guerraoui
1995
Conference Papers

Abstract

Official source

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

About this result

Related concepts (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.

Nuclear proliferation

Nuclear proliferation is the spread of nuclear weapons, fissionable material, and weapons-applicable nuclear technology and information to nations not recognized as "Nuclear Weapon States" by the Treaty on the Non-Proliferation of Nuclear Weapons, commonly known as the Non-Proliferation Treaty or NPT. Proliferation has been opposed by many nations with and without nuclear weapons, as governments fear that more countries with nuclear weapons will increase the possibility of nuclear warfare (up to and including the so-called countervalue targeting of civilians with nuclear weapons), de-stabilize international or regional relations, or infringe upon the national sovereignty of nation states.