The Las-Vegas Processor Identity Problem (How and When to Be Unique)

One of the fundamental problems in distributed computing is how identical processes with identical local memory can choose unique IDs provided they can flip a coin. The variant considered in this paper is the asynchronous shared memory model (atomic registers), and the basic correctness requirement is that upon termination the processes must always have unique IDs.

We study this problem from several viewpoints. On the positive side, we present the first Las-Vegas protocol that solves the problem. The protocol terminates in (optimal) O(log n) expected time, using O(n) shared memory space, where n is the number of participating processes. On the negative side, we show that there is no Las-Vegas protocol if only a bound on n is known, and that no finite-state Las-Vegas protocol can work under schedules that may depend on the history of the shared variable. For the case of arbitrary adversary, we present a Las-Vegas protocol that uses O(n) unbounded registers.

Click here for proceedings version.