Any object made concurrent
A universal construction is a proof and a method showing that any sequential data type with a deterministic specification can be made wait free using a sufficiently powerful primitive. Herlihy proved that consensus is the key, and CAS solves consensus for any number of threads, so CAS is a universal primitive.
How it works
The core idea is to agree on a single serialized order of operations.
- The object state is represented as a sequence of operations or as an immutable snapshot.
- Each thread that wants to apply an operation appends it to a shared log by winning consensus on the next slot.
- Every thread can replay the agreed log from any state to compute the current value, so all threads see the same history.
Because the log order is the linearization order, the construction is automatically linearizable, and adding helping makes it wait free.
Why it matters
Universal construction is mainly a theoretical result: it proves no object is impossible to implement lock free or wait free given CAS. In practice the generic versions are slow, so engineers hand craft specialized structures, but the construction defines the boundary of what is achievable.
Key idea
A universal construction uses consensus, solvable by CAS for any thread count, to agree on a serialized operation log, proving any sequential object can be made wait free and linearizable.