Top

Published in:

2013 | OriginalPaper | Chapter

16. Atomic Consistency (Linearizability)

Author : Michel Raynal

Published in: Distributed Algorithms for Message-Passing Systems

Publisher: Springer Berlin Heidelberg

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

search-config

AI-assisted search

Off

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.

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 Distributed Deadlock Detection

next chapter Sequential Consistency

S. Adve, K. Gharachorloo, Shared memory consistency models. IEEE Comput. 29(12), 66–76 (1996) CrossRef

S. Adve, M. Mill, A unified formalization of four shared memory models. IEEE Trans. Parallel Distrib. Syst. 4(6), 613–624 (1993) CrossRef

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.

P.J. Denning, Virtual memory. ACM Comput. Surv. 2(3), 153–189 (1970) MATHCrossRef

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.

Ch.H. Papadimitriou, The serializability of concurrent database updates. J. ACM 26(4), 631–653 (1979) MathSciNetMATHCrossRef

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

Title: Atomic Consistency (Linearizability)
Author: Michel Raynal
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_16

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner