Asynchronous exclusive selection

DOI10.1145/1400751.1400801zbMATH Open1301.68125arXiv1512.09314OpenAlexW2021785007MaRDI QIDQ2934360FDOQ2934360

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)

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.

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

Recommendations

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

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)

Cited In (9)

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

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)