Adaptive Register Allocation with a Linear Number of Registers

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Leslie Lamport

Abstract: We give an adaptive algorithm in which processes use multi-
writer multi-reader registers to acquire exclusive write access to their own
single-writer, multi-reader registers. It is the first such algorithm that
uses a number of registers linear in the number of participating processes.
Previous adaptive algorithms require at least O(n^{3/2}) registers.

Guest: Eli Gafni

Host: Stefan Schmid