License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.33
URN: urn:nbn:de:0030-drops-191599
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19159/
Go to the corresponding LIPIcs Volume Portal

Taubenfeld, Gadi

Memory-Anonymous Starvation-Free Mutual Exclusion: Possibility and Impossibility Results

pdf-format:
LIPIcs-DISC-2023-33.pdf (0.7 MB)

Abstract

In an anonymous shared memory system, all inter-process communications are via shared objects; however, unlike in standard systems, there is no a priori agreement between processes on the names of shared objects [G. Taubenfeld, 2017; G. Taubenfeld, 2022]. Furthermore, the algorithms are required to be symmetric; that is, the processes should execute precisely the same code, and the only way to distinguish processes is by comparing identifiers for equality. For such a system, read/write registers are called anonymous registers. It is known that symmetric deadlock-free mutual exclusion is solvable for any finite number of processes using anonymous registers [Z. Aghazadeh et al., 2019]. The main question left open in [G. Taubenfeld, 2017; G. Taubenfeld, 2022] is the existence of starvation-free mutual exclusion algorithms for two or more processes. We resolve this open question for memoryless algorithms, in which a process that tries to enter its critical section does not use any information about its previous attempts. Almost all known mutual exclusion algorithms are memoryless. We show that,
1) There is a symmetric memoryless starvation-free mutual exclusion algorithm for two processes using m ≥ 7 anonymous registers if and only if m is odd.
2) There is no symmetric memoryless starvation-free mutual exclusion algorithm for n ≥ 3 processes using (any number of) anonymous registers. Our impossibility result is the only example of a system with fault-free processes, where global progress (i.e., deadlock-freedom) can be ensured, while individual progress to each process (i.e., starvation-freedom) cannot. It complements a known result for systems with failure-prone processes, that there are objects with lock-free implementations but without wait-free implementations [H. Attiya et al., 2022; M. Herlihy, 1991].

BibTeX - Entry

@InProceedings{taubenfeld:LIPIcs.DISC.2023.33,
  author =	{Taubenfeld, Gadi},
  title =	{{Memory-Anonymous Starvation-Free Mutual Exclusion: Possibility and Impossibility Results}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19159},
  URN =		{urn:nbn:de:0030-drops-191599},
  doi =		{10.4230/LIPIcs.DISC.2023.33},
  annote =	{Keywords: anonymous shared memory, memory-anonymous algorithms, anonymous registers, starvation-free mutual exclusion}
}

Keywords: anonymous shared memory, memory-anonymous algorithms, anonymous registers, starvation-free mutual exclusion
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI