Efficient randomized test-and-set implementations

DOI10.1007/S00446-019-00349-ZzbMATH Open1452.68268arXiv1902.04002OpenAlexW2921448733MaRDI QIDQ2010613FDOQ2010613

Authors: George Giakkoupis, Philipp Woelfel 

Publication date: 27 November 2019

Published in: Distributed Computing (Search for Journal in Brave)

Abstract: We study randomized test-and-set (TAS) implementations from registers in the asynchronous shared memory model with n processes. We introduce the problem of group election, a natural variant of leader election, and propose a framework for the implementation of TAS objects from group election objects. We then present two group election algorithms, each yielding an efficient TAS implementation. The first implementation has expected max-step complexity $O(lo{g}^{a}stk)$ in the location-oblivious adversary model, and the second has expected max-step complexity $O(loglogk)$ against any read/write-oblivious adversary, where $kleqn$ is the contention. These algorithms improve the previous upper bound by Alistarh and Aspnes [2] of $O(loglogn)$ expected max-step complexity in the oblivious adversary model. We also propose a modification to a TAS algorithm by Alistarh, Attiya, Gilbert, Giurgiu, and Guerraoui [5] for the strong adaptive adversary, which improves its space complexity from super-linear to linear, while maintaining its $O(logn)$ expected max-step complexity. We then describe how this algorithm can be combined with any randomized TAS algorithm that has expected max-step complexity $T(n)$ in a weaker adversary model, so that the resulting algorithm has $O(logn)$ expected max-step complexity against any strong adaptive adversary and $O(T(n))$ in the weaker adversary model. Finally, we prove that for any randomized 2-process TAS algorithm, there exists a schedule determined by an oblivious adversary such that with probability at least $(1/4{)}^t$ one of the processes needs at least t steps to finish its TAS operation. This complements a lower bound by Attiya and Censor-Hillel [7] on a similar problem for $ngeq3$ processes.

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

Recommendations

• On the time and space complexity of randomized test-and-set
• Sublogarithmic test-and-set against a weak adversary
• Randomized two-process wait-free test-and-set
• Fast randomized test-and-set and renaming
• Test-and-set in optimal space

Mathematics Subject Classification ID

Randomized algorithms (68W20) Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Title not available (Why is that?)
• Analyzing randomized search heuristics: tools from probability theory
• On the importance of having an identity or, is consensus really universal?
• Algorithmic analysis of a basic evolutionary algorithm for continuous optimization
• An \(O(1)\) RMRs leader election algorithm
• Lower bounds for randomized consensus under a weak adversary
• Optimal-time adaptive strong renaming, with applications to counting
• Efficient synchronization of multiprocessors with shared memory
• Efficient adaptive collect using randomization
• On the time and space complexity of randomized test-and-set
• Test-and-Set in Optimal Space
• Sublogarithmic test-and-set against a weak adversary
• Fast randomized test-and-set and renaming
• Title not available (Why is that?)
• Randomized two-process wait-free test-and-set
• The Complexity of Renaming
• Faster randomized consensus with an oblivious adversary

Cited In (2)

• Sublogarithmic test-and-set against a weak adversary
• Short paper: On game-theoretically-fair leader election

This page was built for publication: Efficient randomized test-and-set implementations

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