Publication

Fast Non-Blocking Atomic Commit: An Inherent Trade-off

Rachid Guerraoui, Partha Dutta
2004
Reports

Abstract

This paper investigates the time-complexity of the non-blocking atomic commit (NBAC) problem in a synchronous distributed model where t out of n processes may fail by crashing. We exhibit for t > 3 an inherent trade-off between the fast abort property of NBAC, i.e., aborting a transaction as soon as possible if some process votes no,'' and the fast commit property, i.e., committing a transaction as soon as possible when all processes vote yes'' and no process crashes. We also give two algorithms: the first features fast commit and weak fast abort, whereas the second features fast abort and weak fast commit.

Official source

https://infoscience.epfl.ch/entities/publication/218123a7-53b6-46e5-b7d3-1c716da77e3c

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, Partha Dutta
2004
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/218123a7-53b6-46e5-b7d3-1c716da77e3c

About this result

Related concepts (24)

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.

Concurrency control

In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible. Computer systems, both software and hardware, consist of modules, or components. Each component is designed to operate correctly, i.e., to obey or to meet certain consistency rules.

Spoilt vote

In voting, a ballot is considered spoilt, spoiled, void, null, informal, invalid or stray if a law declares or an election authority determines that it is invalid and thus not included in the vote count. This may occur accidentally or deliberately. The total number of spoilt votes in a United States election has been called the residual vote. In Australia, such votes are generally referred to as informal votes, and in Canada they are referred to as rejected votes. In some jurisdictions spoilt votes are counted and reported.

Related publications (21)

Fast Non-Blocking Atomic Commit: An Inherent Trade-off

Chat with Graph Search

On Estimating the Trace of Quantum State Powers

Microautophagy: definition, classification, and the complexity of the underlying mechanisms

Beyond One Third Byzantine Failures