1 Search Results for "Maor, Liat"

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-dev.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)}
}
  • Refine by Author
  • 1 Maor, Liat
  • 1 Taubenfeld, Gadi

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Distributed computing models
  • 1 Theory of computation → Shared memory algorithms

  • Refine by Keyword
  • 1 Group mutual exclusion
  • 1 RMR complexity
  • 1 compare&swap (CAS)
  • 1 fetch&store (FAS)
  • 1 unbounded number of processes

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact