RANDOMIZED NAMING USING WAIT-FREE SHARED VARIABLES

A naming protocol assigns unique names (keys) to every process out of a set of communicating processes. We construct a randomized wait-free naming protocol using wait-free atomic read/write registers (shared va riables) as process intercommunication primitives. Each process has it s own private register and can read all others. The addresses/names ea ch one uses for the others are possibly different: Processes p and q a ddress the register of process r in a way not known to each other. For n processes and is an element of > 0, the protocol uses a name space of size (1 + is an element of)n and O(n log n log log n) running time (read/writes to shared bits) with probability at least 1-o(1), and O(n log(2) n) overall expected running time. The protocol is based on the wait-free implementation of a novel alpha-Test&SetOnce object that ra ndomly and fast selects a winner from a set of q contenders with proba bility at least alpha in the face of the strongest possible adaptive a dversary.