The Las-Vegas Processor Identity Problem
(How and When to Be Unique)
Shay Kutten Rafail Ostrovsky
Department of Industrial Engineering Bellcore
The Technion rafail@bellcore.com
kutten@ie.technion.ac.il
Boaz Patt-Shamir
Department of Electrical Engineering-Systems
Tel-Aviv University
boaz@eng.tau.ac.il
May 31, 1999
Abstract
We study the classical problem of assigning unique identifiers to identical concurrent processes. In
this paper, we consider the asynchronous shared memory model, and the correctness requirement is that upon
termination of the algorithm, the processes must have unique IDs always. Our results include tight
characterization of the problem in several respects. We call a protocol to this task Las-Vegas if it has
finite expected termination time. Our main positive result is the first Las-Vegas protocol that solves the
problem. The protocol terminates in O(log n) expected asynchronous rounds, using O(n) shared memory space,
where n is the number of participating processes. The new protocol improves on all previous solutions
simultaneously in running time (exponentially), probability of termination (to 1), and space requirement. The
protocol works under the assumption that the asynchronous schedule is oblivious, i.e., independent of the
actual unfolding execution. On the negative side, we show that there is no finite-state Las-Vegas protocol
for the problem if the schedule may depend on the history of the shared memory (an adaptive schedule). We
also show that any Las-Vegas protocol must know n in advance (which implies that crash faults cannot be
tolerated), and that the running time is \Omega (log n). For the case of an arbitrary (non-oblivious)
adversarial schedule, we present a Las-Vegas protocol that uses O(n) unbounded registers. For the read-modify
-write model, we present a constant-space deterministic algorithm.