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

Lecture

Registers and Linearizability

Description

This lecture covers the power of registers in the context of linearizability, discussing the update and scan operations, as well as the concepts of lock-free and wait-free algorithms. It also delves into the SCAN algorithm, exploring its implementation and practical applications.

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

Official source

Related concepts (11)

Non-blocking algorithm

In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.

Linearizability

In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events, that may be extended by adding response events such that: The extended list can be re-expressed as a sequential history (is serializable). That sequential history is a subset of the original unextended list. Informally, this means that the unmodified list of events is linearizable if and only if its invocations were serializable, but some of the responses of the serial schedule have yet to return.

Lock (computer science)

In computer science, a lock or mutex (from mutual exclusion) is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concurrency control policy, and with a variety of possible methods there exists multiple unique implementations for different applications. Generally, locks are advisory locks, where each thread cooperates by acquiring the lock before accessing the corresponding data.

Busy waiting

In computer science and software engineering, busy-waiting, busy-looping or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary on systems that lacked a method of waiting a specific length of time. Processor speeds vary greatly from computer to computer, especially as some processors are designed to dynamically adjust speed based on current workload.

Read-copy-update

In computer science, read-copy-update (RCU) is a synchronization mechanism that avoids the use of lock primitives while multiple threads concurrently read and update elements that are linked through pointers and that belong to shared data structures (e.g., linked lists, trees, hash tables). Whenever a thread is inserting or deleting elements of data structures in shared memory, all readers are guaranteed to see and traverse either the older or the new structure, therefore avoiding inconsistencies (e.g.

Related lectures (9)

Lock-Free Synchronization: Practical Insights Log in to Mediaspace to watch this video

Explores the significance of lock-free synchronization for achieving low latency in distributed systems and discusses practical solutions for unique identifier generation and messaging queues.

The Power of Registers Log in to Mediaspace to watch this video

Covers wait-free implementations of atomic objects, focusing on counters and snapshots, discussing key ideas for enforcing atomicity and wait-freedom.

Anonymous Concurrent Computing Log in to Mediaspace to watch this video

Explores anonymous concurrent computing, covering counters, snapshots, and consensus algorithms.

Lock-Free Synchronization: Performance and Scalability Log in to Mediaspace to watch this video

Explores lock-free synchronization for performance and scalability in distributed systems, covering unique identifier generation, messaging queues, and atomic RDMA reads.

Lock-free synchronization: Achieving low latency Log in to Mediaspace to watch this video