Keynote Talk : Consistency of Distributed Data Structures

Abstract:

Distributed systems are often considered more challenging to program than sequential systems because they entail solving numerous communication related issues. Shared objects, which can be concurrently accessed by the processes, may serve as a practical abstraction of communication. A precise specification of these objects is crucial to ensure their adoption. Finding correct and efficient implementations of common objects (e.g., queues, stacks) is far from trivial and can be even impossible. Intuitively, a « good » implementation of a concurrent object must satisfy two properties: a consistency condition and a progress condition, which respectively specify the meaningfulness of the returned results and the guarantees on liveness.

Linearizability is a consistency condition that ensures all operations in a distributed history appear as if they were executed sequentially: each operation occurs at a single point in time, between its start and end events. This gives processes the illusion of accessing a physical concurrent object. A significant challenge in distributed computing is that wait-free linearizable implementations are often costly, if not impossible. As a result, researchers have explored weak consistency criteria such as PRAM, causal memory, and eventual consistency.