1 Search Results for "Dvir, Rotem"


Document
Mutual Exclusion Algorithms with Constant RMR Complexity and Wait-Free Exit Code

Authors: Rotem Dvir and Gadi Taubenfeld

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)


Abstract
Two local-spinning queue-based mutual exclusion algorithms are presented that have several de- sired properties: (1) their exit codes are wait-free, (2) they satisfy FIFO fairness, (3) they have constant RMR complexity in both the CC and the DSM models, (4) it is not assumed that the number of processes, n, is a priori known, that is, processes may appear or disappear intermit- tently, (5) they use only O(n) shared memory locations, and (6) they make no assumptions on what and how memory is allocated. The algorithms are inspired by J. M. Mellor-Crummey and M. L. Scott famous MCS queue- based algorithm [13] which, except for not having a wait-free exit code, satisfies similar properties. A drawback of the MCS algorithm is that executing the exit code (i.e., releasing a lock) requires spinning – a process executing its exit code may need to wait for the process that is behind it in the queue to take a step before it can proceed. The two new algorithms overcome this drawback while preserving the simplicity and elegance of the original algorithm. Our algorithms use exactly the same atomic instruction set as the original MCS algorithm, namely: read, write, fetch-and-store and compare-and-swap. In our second algorithm it is possible to recycle memory locations so that if there are L mutual exclusion locks, and each process accesses at most one lock at a time, then the algorithm needs only O(L + n) space, as compared to O(Ln) needed by our first algorithm.

Cite as

Rotem Dvir and Gadi Taubenfeld. Mutual Exclusion Algorithms with Constant RMR Complexity and Wait-Free Exit Code. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{dvir_et_al:LIPIcs.OPODIS.2017.17,
  author =	{Dvir, Rotem and Taubenfeld, Gadi},
  title =	{{Mutual Exclusion Algorithms with Constant RMR Complexity and Wait-Free Exit Code}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.17},
  URN =		{urn:nbn:de:0030-drops-86523},
  doi =		{10.4230/LIPIcs.OPODIS.2017.17},
  annote =	{Keywords: Mutual exclusion, locks, local-spinning, cache coherent, distributed shared memory, RMR complexity}
}
  • Refine by Author
  • 1 Dvir, Rotem
  • 1 Taubenfeld, Gadi

  • Refine by Classification

  • Refine by Keyword
  • 1 Mutual exclusion
  • 1 RMR complexity
  • 1 cache coherent
  • 1 distributed shared memory
  • 1 local-spinning
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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