Lecture

The Power of Registers

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.

Description

This lecture explores the concept of wait-free implementations of atomic objects, focusing on counters and snapshots. It covers naive and atomic implementations, discussing the key idea for enforcing atomicity and wait-freedom. The instructor presents examples and compares non-atomic with atomic snapshots.

Official source

Ontological neighbourhood

Computer engineering

High-performance computing: Distributed computing

Related concepts (32)

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.

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.

Concurrent computing

Concurrent computing is a form of computing in which several computations are executed concurrently—during overlapping time periods—instead of sequentially—with one completing before the next starts. This is a property of a system—whether a program, computer, or a network—where there is a separate execution point or "thread of control" for each process. A concurrent system is one where a computation can advance without waiting for all other computations to complete. Concurrent computing is a form of modular programming.

Semaphore (programming)

In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system such as a multitasking operating system. Semaphores are a type of synchronization primitive. A trivial semaphore is a plain variable that is changed (for example, incremented or decremented, or toggled) depending on programmer-defined conditions.

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.

Related lectures (64)

Lock-Free Synchronization: Performance and Scalability

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

Lock-Free Synchronization: Practical Insights

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.

Transactional Memory: Hardware Simplification

Explores transactional memory and hardware simplification for concurrency control in software, emphasizing the benefits of hardware speculation and declarative concurrency.

Scalable Synchronization Mechanisms for Manycore Operating Systems

Explores scalable synchronization mechanisms for many-core operating systems, focusing on the challenges of handling data growth and regressions in OS.

Concurrency Control: Lock-Based Protocols