Asynchronous exclusive selection

DOI10.1145/1400751.1400801MaRDI QIDQ2934360zbMATH OpenOpenAlexFDO

Authors Bogdan S. Chlebus, Dariusz R. Kowalski

Publication date 12 December 2014

Published in Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.09314

zbMATH Keywords

asynchronywait-freerenamingnon-blockingcrashesgraph expansionadaptation to contentionlocal step complexityread-write shared registersstore and collect

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)

Abstract: We consider the task of assigning unique integers to a group of processes in an asynchronous distributed system of a total of $n$ processes prone to crashes that communicate through shared read-write registers. In the Renaming problem, an arbitrary group of $klen$ processes that hold the original names from a range $[N]=1,ldots,N$, contend to acquire unique integers in a smaller range $[M]$ as new names using some $r$ auxiliary shared registers. We give number of wait-free renaming algorithms, in particular an adaptive one having $M=8k-lgk-1$ as a bound on the range of new names that operates in $O(k)$ local steps and uses $r=O(n^2)$ registers. As a lower bound, we show that a wait-free solution to Renaming requires $1+mink-2,lfloorlo{g}_{2r}fracNM+k-1floor$ steps in the worst case. We apply renaming algorithms to obtain solutions to Store&Collect problem, which is about a group of $klen$ processes with the original names in a range $[N]$ proposing individual values (operation Store) and returning a view of all proposed values (operation Collect), while using some $r$ auxiliary shared read-write registers. We consider a problem Mining-Names, in which processes may repeatedly request positive integers as new names subject to the constraints that no integer can be assigned to different processes and the number of integers never acquired as names is finite in an infinite execution. We give two solutions to Mining-Names in a distributed system in which there are infinitely many shared read-write registers available. A non-blocking solution leaves at most $2n-2$ nonnegative integers never assigned as names, and a wait-free algorithm leaves at most $(n+2)(n-1)$ nonnegative integers never assigned as names.

Recommendations

• Simultaneous selection
• Parallel selection
• FUNCTIONAL PEARL Concurrent distinct choices
• scientific article; zbMATH DE number 4213428
• Selection without exclusion
• Asynchronous group mutual exclusion
• A parallel selection algorithm
• Discrete asynchronous iterations
• Synchronizing the asynchronous

Cited in

(9)

• Asynchronous coordination under preferences and constraints
• Anonymous processors with synchronous shared memory: Monte Carlo algorithms
• Tight bounds for asynchronous renaming
• Brief announcement: Asynchronous coordination with constraints and preferences
• Randomized naming using wait-free shared variables
• Renaming in an asynchronous environment
• Fully-adaptive algorithms for long-lived renaming
• The renaming problem in shared memory systems: an introduction
• Deterministic multi-channel information exchange

This page was built for publication: Asynchronous exclusive selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934360)