The Las-Vegas Processor Identity Problem
Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir.
Abstract:
One of the central 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 unless n is known precisely, 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 an arbitrary adversary, we present a Las-Vegas protocol that uses O(n) unbounded registers.
comment: Appeared In Proceedings of the Second Israel Symposium on Theory of Computing and Systems (ISTCS-93)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |