Lecture

Terminating Reliable Broadcast & NBAC

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.

In course

CS-451: Distributed algorithms

Computing is nowadays distributed over several machines, in a local IP-like network, a cloud or a P2P network. Failures are common and computations need to proceed despite partial failures of machines or communication links. This course will study the fo ...

Description

This lecture covers Terminating Reliable Broadcast (TRB) and Non-Blocking Atomic Commit (NBAC). TRB is a communication primitive used to disseminate messages reliably among processes, while NBAC focuses on reaching agreement on committing or aborting transactions in a distributed system. The lecture explains the concepts, algorithms, and properties of TRB and NBAC, including integrity, validity, agreement, termination, and consensus. It also discusses the use of failure detectors and consensus algorithms in achieving non-blocking atomic commit. The presentation concludes with a historical overview of atomic commit protocols and their complexities.

Instructor

Rachid Guerraoui

Rachid Guerraoui has been affiliated with Ecole des Mines of Paris, the Commissariat à l'Energie Atomique of Saclay, Hewlett Packard Laboratories and the Massachusetts Institute of Technology. He has worked in a variety of aspects of distributed computing, including distributed algorithms and distributed programming languages. He is most well known for his work on (e-)Transactions, epidemic information dissemination and indulgent algorithms. He co-authored a book on Transactional Systems (Hermes) and a book on reliable distributed programming (Springer). He was appointed program chair of ECOOP 1999, ACM Middleware 2001, IEEE SRDS 2002, DISC 2004 and ACM PODC 2010. His publications are available at http://lpdwww.epfl.ch/rachid/papers/generalPublis.html

Official source

Ontological neighbourhood

Computer engineering

High-performance computing: Distributed computing

Related concepts (31)

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.

Three-phase commit protocol

In computer networking and databases, the three-phase commit protocol (3PC) is a distributed algorithm which lets all nodes in a distributed system agree to commit a transaction. It is a more failure-resilient refinement of the two-phase commit protocol (2PC). A two-phase commit protocol cannot dependably recover from a failure of both the coordinator and a cohort member during the Commit phase. If only the coordinator had failed, and no cohort members had received a commit message, it could safely be inferred that no commit had happened.

Commit (data management)

In computer science and data management, a commit is the making of a set of tentative changes permanent, marking the end of a transaction and providing Durability to ACID transactions. A commit is an act of committing. The record of commits is called the commit log. In terms of transactions, the opposite of commit is to discard the tentative changes of a transaction, a rollback. The transaction, commit and rollback concepts are key to the ACID property of databases.

Database transaction

A database transaction symbolizes a unit of work, performed within a database management system (or similar system) against a database, that is treated in a coherent and reliable way independent of other transactions. A transaction generally represents any change in a database. Transactions in a database environment have two main purposes: To provide reliable units of work that allow correct recovery from failures and keep a database consistent even in cases of system failure.

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.

Related lectures (64)

Architecture of CockroachDB

Explores the architecture of CockroachDB, focusing on transaction management, concurrency control, and scalability.

Version Control System: Basics and Workflow

Introduces the basics of Version Control Systems, focusing on Git operations and branching strategies.

Transactions: Concepts and Implementations

Explores the elegance and challenges of transactions, including ACID properties and transactional memory benefits in concurrent programming.

Version Control with Git

Introduces version control with Git, focusing on repository setup, committing changes, and collaboration.

Distributed Transactions: Coordination, Concurrency Control, and Recovery