Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Basic Definitions and Network Traversal Algorithms Read chapter Read first chapter

2013 | OriginalPaper | Chapter

10. Permission-Based Mutual Exclusion Algorithms

Author : Michel Raynal

Published in: Distributed Algorithms for Message-Passing Systems

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This chapter is on one of the most important synchronization problems, namely mutual exclusion. This problem (whose name is usually shortened to “mutex”) consists of ensuring that at most one process at a time is allowed to access some resource (which can be a physical or a virtual resource).
After having defined the problem, the chapter presents two approaches which allow us to solve it. Both are based on permissions given by processes to other processes. The algorithms of the first approach are based on individual permissions, while the algorithms of the second approach are based on arbiter permissions (arbiter-based algorithms are also called quorum-based algorithms).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Simulating Synchrony on Top of Asynchronous Systems
next chapter Distributed Resource Allocation
Literature
7.
D. Agrawal, A. El Abbadi, An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Trans. Comput. Syst. 9(1), 1–20 (1991) CrossRef
9.
M. Ahamad, M.H. Ammar, S.Y. Cheung, Multidimensional voting. ACM Trans. Comput. Syst. 9(4), 399–431 (1991) CrossRef
41.
D. Barbara, H. Garcia Molina, Mutual exclusion in partitioned distributed systems. Distrib. Comput. 1(2), 119–132 (1986) CrossRef
42.
D. Barbara, H. Garcia Molina, A. Spauster, Increasing availability under mutual exclusion constraints with dynamic vote assignments. ACM Trans. Comput. Syst. 7(7), 394–426 (1989) CrossRef
68.
G. Cao, M. Singhal, A delay-optimal quorum-based mutual exclusion algorithm for distributed systems. IEEE Trans. Parallel Distrib. Syst. 12(12), 1256–1268 (1991)
70.
O. Carvalho, G. Roucairol, On the distribution of an assertion, in Proc. First ACM Symposium on Principles of Distributed Computing (PODC’1982) (ACM Press, New York, 1982), pp. 18–20
71.
O. Carvalho, G. Roucairol, On mutual exclusion in computer networks. Commun. ACM 26(2), 146–147 (1983) CrossRef
78.
K.M. Chandy, J. Misra, The drinking philosophers problem. ACM Trans. Program. Lang. Syst. 6(4), 632–646 (1984) CrossRef
109.
E.W. Dijkstra, Solution of a problem in concurrent programming control. Commun. ACM 8(9), 569 (1965) CrossRef
147.
159.
D.K. Gifford, Weighted voting for replicated data, in Proc. 7th ACM Symposium on Operating System Principles (SOSP’79) (ACM Press, New York, 1979), pp. 150–172
176.
J.-M. Hélary, N. Plouzeau, M. Raynal, A distributed algorithm for mutual exclusion in arbitrary networks. Comput. J. 31(4), 289–295 (1988) MathSciNetMATHCrossRef
195.
T. Ibaraki, T. Kameda, A theory of coteries: mutual exclusion in distributed systems. J. Parallel Distrib. Comput. 4(7), 779–794 (1993)
226.
L. Lamport, Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978) MATHCrossRef
239.
S. Lodha, A.D. Ksemkalyani, A fair distributed mutual exclusion algorithm. IEEE Trans. Parallel Distrib. Syst. 11(6), 537–549 (2000) CrossRef
243.
M. Maekawa, A \(\sqrt{n}\) algorithm for mutual exclusion in decentralized systems. ACM Trans. Comput. Syst. 3(2), 145–159 (1985) CrossRef
277.
281.
M.L. Neilsen, M. Masaaki, M. Raynal, A general method to define quorums, in Proc. 12th Int’l IEEE Conference on Distributed Computing Systems (ICDCS’92) (IEEE Press, New York, 1992), pp. 657–664 CrossRef
282.
M. Nesterenko, M. Mizuno, A quorum-based self-stabilizing distributed mutual exclusion algorithm. J. Parallel Distrib. Comput. 62(2), 284–305 (2002) MATHCrossRef
294.
D. Peleg, A. Wool, Crumbling walls: a class of practical and efficient quorum systems. Distrib. Comput. 10(2), 87–97 (1997) CrossRef
306.
M. Raynal, Algorithms for Mutual Exclusion (The MIT Press, Cambridge, 1986), 107 pages. ISBN 0-262-18119-3 MATH
310.
M. Raynal, A simple taxonomy of distributed mutual exclusion algorithms. Oper. Syst. Rev. 25(2), 47–50 (1991) CrossRef
317.
M. Raynal, Concurrent Programming: Algorithms, Principles, and Foundations (Springer, Berlin, 2012), 500 pages. ISBN 978-3-642-32026-2
327.
G. Ricart, A.K. Agrawala, An optimal algorithm for mutual exclusion in computer networks. Commun. ACM 24(1), 9–17 (1981) MathSciNetCrossRef
333.
B. Sanders, The information structure of distributed mutual exclusion algorithms. ACM Trans. Comput. Syst. 5(3), 284–299 (1987) CrossRef
347.
M. Singhal, A class of deadlock-free Maekawa-type algorithms for mutual exclusion in distributed systems. Distrib. Comput. 4(3), 131–138 (1991) MATHCrossRef
348.
M. Singhal, A dynamic information-structure mutual exclusion algorithm for distributed systems. IEEE Trans. Parallel Distrib. Syst. 3(1), 121–125 (1992) CrossRef
349.
M. Singhal, A taxonomy of distributed mutual exclusion. J. Parallel Distrib. Comput. 18(1), 94–101 (1993) MATHCrossRef
362.
G. Taubenfeld, Synchronization Algorithms and Concurrent Programming (Pearson Prentice-Hall, Upper Saddle River, 2006), 423 pages. ISBN 0-131-97259-6
368.
R.H. Thomas, A majority consensus approach to concurrency control for multiple copy databases. ACM Trans. Database Syst. 4(2), 180–209 (1979) CrossRef
380.
M. Vukolić, Quorum Systems with Applications to Storage and Consensus (Morgan & Claypool, San Francisco, 2012), 130 pages. ISBN 798-1-60845-683-3
Metadata
Title
Permission-Based Mutual Exclusion Algorithms
Author
Michel Raynal
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
Book
Distributed Algorithms for Message-Passing Systems

Print ISBN: 978-3-642-38122-5

Electronic ISBN: 978-3-642-38123-2

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-3-642-38123-2_10

Premium Partner

    Image Credits