How and When to Be Unique
Title | How and When to Be Unique |
Publication Type | Technical Report |
Year of Publication | 1993 |
Authors | Kutten, S., Ostrovsky R., & Patt-Shamir B. |
Other Numbers | 862 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-074.pdf |
Bibliographic Notes | ICSI Technical Report TR-93-074 |
Abbreviated Authors | S. Kutten, R. Ostrovsky, and B. Patt-Shamir |
ICSI Publication Type | Technical Report |