Central Library, Indian Institute of Technology Delhi
केंद्रीय पुस्तकालय, भारतीय प्रौद्योगिकी संस्थान दिल्ली

Principles of transactional memory [electronic resource] / Rachid Guerraoui and Michał Kapałka.

By: Guerraoui, RachidContributor(s): Kapałka, MichałMaterial type: TextTextSeries: Synthesis digital library of engineering and computer science | Synthesis lectures on distributed computing theory ; # 4.Publication details: San Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA) :: Morgan & Claypool,, c2010Description: 1 electronic text (xii, 179 p. : ill.) : digital fileISBN: 9781608450121 (electronic bk.)Subject(s): Transaction systems (Computer systems) | Threads (Computer programs) | Synchronization | Parallel programming (Computer science) | transactional memory | concurrent programming | shared memory | theoryDDC classification: 005.2 LOC classification: QA76.642 | .G846 2010Online resources: Abstract with links to resource Also available in print.
Contents:
1. Introduction -- Problems with explicit locking -- Transactional memory -- Scope of this book -- Contents --
Part I. Basics -- 2. Shared memory systems -- Basic abstractions -- Processes and shared objects -- Shared object implementations -- Executions of concurrent algorithms -- Histories -- Semantics of base objects -- Configurations and indistinguishability -- Asynchrony and wait-freedom -- Computability questions -- Summary of notation --
3. Transactional memory: a primer -- TM shared object -- Transactions -- T-objects and their semantics -- TM histories -- Status of transactions -- Real-time order -- Conflicts -- Restrictions -- High-level TM API -- Discussion -- Nested transactions -- Non-transactional access to T-objects -- False conflicts -- A transaction abstraction -- Summary of notation --
4. TM correctness issues -- Atomicity of committed transactions -- Real-time order -- Precluding inconsistent views --
5. Implementing ATM -- General idea -- (Read-write) try-locks -- Phase locking TM algorithm -- An improved TM algorithm -- Alternative implementation techniques -- Obstruction-free mechanisms -- Validation heuristics -- Contention management -- Multi-version schemes -- Deferred updates --
6. Further reading -- Shared memory systems -- Transactional memory --
Part II. Safety -- 7. Opacity -- Opacity step by step -- Definition of opacity -- Examples --
8. Proving opacity: an example -- Preliminaries -- A graph characterization of opacity -- 2-phase locking TM -- TM with invisible reads --
9. Opacity vs. atomicity -- Properties of TM implementations -- Complexity lower bound -- Circumventing the lower bound --
10. Further reading -- The roots of opacity -- Alternatives and extensions of opacity --
Part III. Progress -- 11. The liveness of ATM --
12. Lock-based TMs -- Strong progressiveness -- Verifying strong progressiveness -- Strong try-locks -- Reduction theorem -- Examples -- The computational power of a lock-based TM -- Equivalence between lock-based TMs and try-locks -- The computational power of a strong try-lock -- Weakening strong progressiveness --
13. Obstruction-free TMs -- Obstruction-freedom -- Implementing an OFTM -- The computational power of an OFTM -- Definition of an Fo-consensus object -- Implementing an OFTM from fo-consensus objects -- Equivalence between OFTMs and Fo-consensus objects -- The power of an Fo-consensus object -- Impossibility of strict disjoint-access-parallelism -- Alternative forms of obstruction-freedom --
14. General liveness of TMs -- High-level liveness of a TM -- Preliminaries -- Definition of (high-level) TM liveness -- Examples of TM liveness properties -- Classes of TM liveness properties -- Impossibility result -- Ensuring non-(n - 1), prioritizing TM liveness properties -- Summary and discussion --
15. Further reading --
16. Conclusions -- Bibliography -- Authors' biographies.
Abstract: Transactional memory (TM) is an appealing paradigm for concurrent programming on shared memory architectures. With a TM, threads of an application communicate, and synchronize their actions, via in-memory transactions. Each transaction can perform any number of operations on shared data, and then either commit or abort. When the transaction commits, the effects of all its operations become immediately visible to other transactions; when it aborts, however, those effects are entirely discarded. Transactions are atomic: programmers get the illusion that every transaction executes all its operations instantaneously, at some single and unique point in time. Yet, a TM runs transactions concurrently to leverage the parallelism offered by modern processors. The aim of this book is to provide theoretical foundations for transactional memory. This includes defining a model of a TM, as well as answering precisely when a TM implementation is correct, what kind of properties it can ensure, what are the power and limitations of a TM, and what inherent trade-offs are involved in designing a TM algorithm. While the focus of this book is on the fundamental principles, its goal is to capture the common intuition behind the semantics of TMs and the properties of existing TM implementations.
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Item type Current library Call number Status Date due Barcode
Ebooks Ebooks Indian Institute of Technology Delhi - Central Library
Available

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Part of: Synthesis digital library of engineering and computer science.

Series from website.

Includes bibliographical references (p. 171-178).

1. Introduction -- Problems with explicit locking -- Transactional memory -- Scope of this book -- Contents --

Part I. Basics -- 2. Shared memory systems -- Basic abstractions -- Processes and shared objects -- Shared object implementations -- Executions of concurrent algorithms -- Histories -- Semantics of base objects -- Configurations and indistinguishability -- Asynchrony and wait-freedom -- Computability questions -- Summary of notation --

3. Transactional memory: a primer -- TM shared object -- Transactions -- T-objects and their semantics -- TM histories -- Status of transactions -- Real-time order -- Conflicts -- Restrictions -- High-level TM API -- Discussion -- Nested transactions -- Non-transactional access to T-objects -- False conflicts -- A transaction abstraction -- Summary of notation --

4. TM correctness issues -- Atomicity of committed transactions -- Real-time order -- Precluding inconsistent views --

5. Implementing ATM -- General idea -- (Read-write) try-locks -- Phase locking TM algorithm -- An improved TM algorithm -- Alternative implementation techniques -- Obstruction-free mechanisms -- Validation heuristics -- Contention management -- Multi-version schemes -- Deferred updates --

6. Further reading -- Shared memory systems -- Transactional memory --

Part II. Safety -- 7. Opacity -- Opacity step by step -- Definition of opacity -- Examples --

8. Proving opacity: an example -- Preliminaries -- A graph characterization of opacity -- 2-phase locking TM -- TM with invisible reads --

9. Opacity vs. atomicity -- Properties of TM implementations -- Complexity lower bound -- Circumventing the lower bound --

10. Further reading -- The roots of opacity -- Alternatives and extensions of opacity --

Part III. Progress -- 11. The liveness of ATM --

12. Lock-based TMs -- Strong progressiveness -- Verifying strong progressiveness -- Strong try-locks -- Reduction theorem -- Examples -- The computational power of a lock-based TM -- Equivalence between lock-based TMs and try-locks -- The computational power of a strong try-lock -- Weakening strong progressiveness --

13. Obstruction-free TMs -- Obstruction-freedom -- Implementing an OFTM -- The computational power of an OFTM -- Definition of an Fo-consensus object -- Implementing an OFTM from fo-consensus objects -- Equivalence between OFTMs and Fo-consensus objects -- The power of an Fo-consensus object -- Impossibility of strict disjoint-access-parallelism -- Alternative forms of obstruction-freedom --

14. General liveness of TMs -- High-level liveness of a TM -- Preliminaries -- Definition of (high-level) TM liveness -- Examples of TM liveness properties -- Classes of TM liveness properties -- Impossibility result -- Ensuring non-(n - 1), prioritizing TM liveness properties -- Summary and discussion --

15. Further reading --

16. Conclusions -- Bibliography -- Authors' biographies.

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

INSPEC

Google scholar

Google book search

Transactional memory (TM) is an appealing paradigm for concurrent programming on shared memory architectures. With a TM, threads of an application communicate, and synchronize their actions, via in-memory transactions. Each transaction can perform any number of operations on shared data, and then either commit or abort. When the transaction commits, the effects of all its operations become immediately visible to other transactions; when it aborts, however, those effects are entirely discarded. Transactions are atomic: programmers get the illusion that every transaction executes all its operations instantaneously, at some single and unique point in time. Yet, a TM runs transactions concurrently to leverage the parallelism offered by modern processors. The aim of this book is to provide theoretical foundations for transactional memory. This includes defining a model of a TM, as well as answering precisely when a TM implementation is correct, what kind of properties it can ensure, what are the power and limitations of a TM, and what inherent trade-offs are involved in designing a TM algorithm. While the focus of this book is on the fundamental principles, its goal is to capture the common intuition behind the semantics of TMs and the properties of existing TM implementations.

Also available in print.

Title from PDF t.p. (viewed on October 13, 2010).

There are no comments on this title.

to post a comment.
Copyright © 2022 Central Library, Indian Institute of Technology Delhi. All Rights Reserved.

Powered by Koha