The Las-Vegas processor identity problem (How and when to be unique)

We study the classical problem of assigning unique identifiers to identical concurrent processes. In this paper, we consider the asynchronous shared m emory model, and the correctness requirement is that upon termination of th e algorithm, the processes must have unique IDs always. Our results include tight characterization of the problem in several respects. We call a proto col solving this task Las Vegas if it has finite expected termination time. Our main positive result is the first Las-Vegas protocol that solves the p roblem. The protocol terminates in O(log n) expected asychronous rounds, us ing O(n) shared memory space, where n is the number of participating proces ses. 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-slate Las-Vegas prot ocol for the problem if the schedule may depend on the history of the share d memory tan adaptive schedule). We also show that any Las-Vegas protocol m ust know n in advance (which implies that crash faults cannot be tolerated) and that the running time is n(log n). For the case of an arbitrary (nonob livious) adversarial schedule, we present a Las-Vegas protocol that uses O( n) unbounded registers. For the read-modify-write model, we present a const ant-space deterministic algorithm, (C) 2000 Academic Press.