Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Basic Definitions and Network Traversal Algorithms Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

16. Atomic Consistency (Linearizability)

verfasst von : Michel Raynal

Erschienen in: Distributed Algorithms for Message-Passing Systems

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This chapter is on the strongest consistency condition for concurrent objects. This condition is called atomicity when considering shared registers, and linearizability when considering more sophisticated types of objects. In the following, these two terms are considered as synonyms.
The chapter first introduces the notion of a distributed shared memory. It then defines formally the atomicity concept, and presents its main composability property, and several implementations on top of a message-passing system.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Distributed Deadlock Detection
Nächstes Kapitel Sequential Consistency
Literatur
3.
S. Adve, K. Gharachorloo, Shared memory consistency models. IEEE Comput. 29(12), 66–76 (1996) CrossRef
4.
S. Adve, M. Mill, A unified formalization of four shared memory models. IEEE Trans. Parallel Distrib. Syst. 4(6), 613–624 (1993) CrossRef
5.
Y. Afek, G.M. Brown, M. Merritt, Lazy caching. ACM Trans. Program. Lang. Syst. 15(1), 182–205 (1993) CrossRef
10.
M. Ahamad, G. Neiger, J.E. Burns, P.W. Hutto, P. Kohli, Causal memory: definitions, implementation and programming. Distrib. Comput. 9, 37–49 (1995) MathSciNetCrossRef
21.
H. Attiya, S. Chaudhuri, R. Friedman, J.L. Welch, Non-sequential consistency conditions for shared memory, in Proc. 5th ACM Symposium on Parallel Algorithms and Architectures (SPAA’93) (ACM Press, New York, 1993), pp. 241–250
23.
H. Attiya, J.L. Welch, Sequential consistency versus linearizability. ACM Trans. Comput. Syst. 12(2), 91–122 (1994) CrossRef
32.
H.E. Bal, F. Kaashoek, A. Tanenbaum, Orca: a language for parallel programming of distributed systems. IEEE Trans. Softw. Eng. 18(3), 180–205 (1992) CrossRef
69.
N. Carriero, D. Gelernter, T.G. Mattson, A.H. Sherman, The Linda alternative to message-passing systems. Parallel Comput. 20(4), 633–655 (1994) MATHCrossRef
72.
L.M. Censier, P. Feautrier, A new solution to coherence problems in multicache systems. IEEE Trans. Comput. C-27(12), 112–118 (1978) CrossRef
106.
119.
M. Dubois, C. Scheurich, Memory access dependencies in shared memory multiprocessors. IEEE Trans. Softw. Eng. 16(6), 660–673 (1990) CrossRef
136.
R. Friedman, Implementing hybrid consistency with high-level synchronization operations, in Proc. 12th Annual ACM Symposium on Principles of Distributed Computing (PODC’93) (ACM Press, New York, 1993), pp. 229–240
151.
V.K. Garg, M. Raynal, Normality: a consistency condition for concurrent objects. Parallel Process. Lett. 9(1), 123–134 (1999) CrossRef
157.
K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta, J.L. Hennessy, Memory consistency and event ordering in scalable shared memory multiprocessors, in Proc. 17th ACM Int’l Symposium on Computer Architecture (ISCA’90) (1990), pp. 15–26 CrossRef
183.
M. Herlihy, J. Wing, Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990) CrossRef
194.
P. Hutto, M. Ahamad, Slow memory: weakening consistency to enhance concurrency in distributed shared memories, in Proc. 10th IEEE Int’l Conference on Distributed Computing Systems (ICDCS’90) (IEEE Press, New York, 1990), pp. 302–311
200.
E. Jiménez, A. Fernández, V. Cholvi, A parameterized algorithm that implements sequential, causal, and cache memory consistencies. J. Syst. Softw. 81(1), 120–131 (2008) CrossRef
204.
P. Keleher, A.L. Cox, W. Zwaenepoel, Lazy release consistency for software distributed shared memory, in Proc. 19th ACM Int’l Symposium on Computer Architecture (ISCA’92), (1992), pp. 13–21 CrossRef
212.
R. Kordale, M. Ahamad, A scalable technique for implementing multiple consistency levels for distributed objects, in Proc. 16th IEEE Int’l Conference on Distributed Computing Systems (ICDCS’96) (IEEE Press, New York, 1996), pp. 369–376 CrossRef
227.
L. Lamport, How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput. C-28(9), 690–691 (1979) CrossRef
228.
L. Lamport, On inter-process communications, part I: basic formalism. Distrib. Comput. 1(2), 77–85 (1986) MATHCrossRef
229.
L. Lamport, On inter-process communications, part II: algorithms. Distrib. Comput. 1(2), 86–101 (1986) MATHCrossRef
234.
K. Li, K.P. Huda, Memory coherence in shared virtual memory systems. ACM Trans. Comput. Syst. 7(4), 321–359 (1989) CrossRef
237.
R.J. Lipton, J.S. Sandberg, PRAM: a scalable shared memory. Tech Report CS-TR-180-88, Princeton University, 1988
256.
M. Mavronicolas, D. Roth, Efficient, strong consistent implementations of shared memory, in Proc. 6th Int’l Workshop on Distributed Algorithms (WDAG’92). LNCS, vol. 647 (Springer, Berlin, 1992), pp. 346–361 CrossRef
262.
J. Misra, Axioms for memory access in asynchronous hardware systems. ACM Trans. Program. Lang. Syst. 8(1), 142–153 (1986) MATHCrossRef
267.
N. Mittal, V.K. Garg, Consistency conditions for multi-objects operations, in Proc. 18th IEEE Int’l Conference on Distributed Computing Systems (ICDCS’98) (IEEE Press, New York, 1998), pp. 582–589
286.
B. Nitzberg, V. Lo, Distributed shared memory: a survey of issues and algorithms. IEEE Comput. 24(8), 52–60 (1991) CrossRef
289.
301.
J. Protic, M. Tomasevic, Distributed shared memory: concepts and systems. IEEE Concurr. 4(2), 63–79 (1996)
313.
M. Raynal, Sequential consistency as lazy linearizability, in Proc. 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA’02) (ACM Press, New York, 2002), pp. 151–152
323.
M. Raynal, A. Schiper, A suite of formal definitions for consistency criteria in distributed shared memories, in Proc. 9th Int’l IEEE Conference on Parallel and Distributed Computing Systems (PDCS’96) (IEEE Press, New York, 1996), pp. 125–131
326.
M. Raynal, K. Vidyasankar, A distributed implementation of sequential consistency with multi-object operations, in Proc. 24th IEEE Int’l Conference on Distributed Computing Systems (ICDCS’04) (IEEE Press, New York, 2004), pp. 544–551 CrossRef
371.
F. Torres-Rojas, M. Ahamad, M. Raynal, Lifetime-based consistency protocols for distributed objects, in Proc. 12th Int’l Symposium on Distributed Computing (DISC’98). LNCS, vol. 1499 (Springer, Berlin, 1998), pp. 378–392
372.
F. Torres-Rojas, M. Ahamad, M. Raynal, Timed consistency for shared distributed objects, in Proc. 18th Annual ACM Symposium on Principles of Distributed Computing (PODC’99) (ACM Press, New York, 1999), pp. 163–172
Metadaten
Titel
Atomic Consistency (Linearizability)
verfasst von
Michel Raynal
Copyright-Jahr
2013
Verlag
Springer Berlin Heidelberg
Buch
Distributed Algorithms for Message-Passing Systems

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

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

Copyright-Jahr: 2013

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