Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Terminating Reliable Broadcast & NBAC

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.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

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 (32)

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.

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.

Atomic commit

In the field of computer science, an atomic commit is an operation that applies a set of distinct changes as a single operation. If the changes are applied, then the atomic commit is said to have succeeded. If there is a failure before the atomic commit can be completed, then all of the changes completed in the atomic commit are reversed. This ensures that the system is always left in a consistent state. The other key property of isolation comes from their nature as atomic operations.

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.

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.

Related lectures (32)

Gitlab Agent for Kubernetes (`agentk`)

Covers the setup of a Gitlab agent for Kubernetes, focusing on installation, version control, and troubleshooting.

Replication and Consensus in Distributed Systems

Explores replication, consensus, Paxos algorithm, majoritarian consensus, and time-stop reservation in distributed systems.

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Architecture of CockroachDB Log in to Mediaspace to watch this video

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

Distributed Transactions: Principles and Protocols Log in to Mediaspace to watch this video