Abstract.
A naming protocol assigns unique names (keys) to every process out of a set of communicating processes. We construct a randomized wait-free naming protocol using wait-free atomic read/write registers (shared variables) as process intercommunication primitives. Each process has its own private register and can read all others. The addresses/names each one uses for the others are possibly different: Processes p and q address the register of process r in a way not known to each other. For \(n\) processes and \(\epsilon > 0\), the protocol uses a name space of size \((1+\epsilon)n\) and \(O(n \log n \log \log n)\) running time (read/writes to shared bits) with probability at least \(1-o(1)\), and \(O(n \log^2 n)\) overall expected running time. The protocol is based on the wait-free implementation of a novel \(\alpha\)-Test&SetOnce object that randomly and fast selects a winner from a set of q contenders with probability at least \(\alpha\) in the face of the strongest possible adaptive adversary.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: September 1994 / Accepted: January 1998
Rights and permissions
About this article
Cite this article
Panconesi, A., Papatriantafilou, M., Tsigas, P. et al. Randomized naming using wait-free shared variables. Distrib Comput 11, 113–124 (1998). https://doi.org/10.1007/s004460050045
Issue Date:
DOI: https://doi.org/10.1007/s004460050045