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.2021.30
URN: urn:nbn:de:0030-drops-148322
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14832/
Go to the corresponding LIPIcs Volume Portal

Maor, Liat ; Taubenfeld, Gadi

Constant RMR Group Mutual Exclusion for Arbitrarily Many Processes and Sessions

pdf-format:
LIPIcs-DISC-2021-30.pdf (0.7 MB)

Abstract

Group mutual exclusion (GME), introduced by Joung in 1998, is a natural synchronization problem that generalizes the classical mutual exclusion and readers and writers problems. In GME a process requests a session before entering its critical section; processes are allowed to be in their critical sections simultaneously provided they have requested the same session.
We present a GME algorithm that (1) is the first to achieve a constant Remote Memory Reference (RMR) complexity for both cache coherent and distributed shared memory machines; and (2) is the first that can be accessed by arbitrarily many dynamically allocated processes and with arbitrarily many session names. Neither of the existing GME algorithms satisfies either of these two important properties. In addition, our algorithm has constant space complexity per process and satisfies the two strong fairness properties, first-come-first-served and first-in-first-enabled. Our algorithm uses an atomic instruction set supported by most modern processor architectures, namely: read, write, fetch-and-store and compare-and-swap.

BibTeX - Entry

@InProceedings{maor_et_al:LIPIcs.DISC.2021.30,
  author =	{Maor, Liat and Taubenfeld, Gadi},
  title =	{{Constant RMR Group Mutual Exclusion for Arbitrarily Many Processes and Sessions}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14832},
  URN =		{urn:nbn:de:0030-drops-148322},
  doi =		{10.4230/LIPIcs.DISC.2021.30},
  annote =	{Keywords: Group mutual exclusion, RMR complexity, unbounded number of processes, fetch\&store (FAS), compare\&swap (CAS)}
}

Keywords: Group mutual exclusion, RMR complexity, unbounded number of processes, fetch&store (FAS), compare&swap (CAS)
Collection: 35th International Symposium on Distributed Computing (DISC 2021)
Issue Date: 2021
Date of publication: 04.10.2021

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