DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2021.30

Constant RMR Group Mutual Exclusion for Arbitrarily Many Processes and Sessions

Authors: Liat Maor and Gadi Taubenfeld

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

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.

Cite as

Liat Maor and Gadi Taubenfeld. Constant RMR Group Mutual Exclusion for Arbitrarily Many Processes and Sessions. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.DISC.2021.30},
  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)}
}

Search Results

Documents authored by Maor, Liat

Constant RMR Group Mutual Exclusion for Arbitrarily Many Processes and Sessions

Abstract

Cite as

Thanks for your feedback!

Could not send message