How and When to Be Unique

TitleHow and When to Be Unique
Publication TypeTechnical Report
Year of Publication1993
AuthorsKutten, S., Ostrovsky R., & Patt-Shamir B.
Other Numbers862

One of the fundamental problems in distributed computing is how identical processors 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 protocol that solves the problem and terminates with probability 1. 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 no protocol can terminate with probability 1 if n is unknown, and that no finite-state protocol can terminate with probability 1 if the schedule is non-oblivious (i.e., may depend on the history of the shared variable).We also discuss the dynamic setting (where processes may join and leave the system dynamically), and give a deterministic protocol for the read-modify-write model that needs only 3 shared bits.

Bibliographic Notes

ICSI Technical Report TR-93-074

Abbreviated Authors

S. Kutten, R. Ostrovsky, and B. Patt-Shamir

ICSI Publication Type

Technical Report