ISSN:
1432-0452
Keywords:
Key words: Naming problem – Symmetry breaking – Unique process ID – Asynchronous distributed protocols – Fault-tolerance – Shared memory – Wait-free read/write registers – Atomicity – Test-and-set objects – Randomized algorithms – Adaptive adversary
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004460050045
Permalink
