1

Lahore Garrison University

Parallel and Distributed
Computing
Session Fall-2020

Lecture – 03 Week – 02
INSTRUCTOR: MUHAMMAD ARSALAN RAZA
 2

Lahore Garrison University

NAME: EMAIL: PHONE NUMBER: VISITING HOURS:
MUHAMMAD ARSALAN RAZA MARSALANRAZA@LGU.EDU.P 0333-7843180 (PRIMARY) MON-FRIDAY:(12:30PM-3:00PM)
K 0321-4069289 THURSDAY: (9:30AM-3:00PM)
 3
Preamble

 DS Communication Terminology

 Synchronous and Asynchronous Communication

 Synchronous vs. Asynchronous communication

Lahore Garrison University

 4
Lesson Plan

 Introduction to transactions
 The Transaction Model
 A.C.I.D
 Types of Transactions
 Nested Transactions vs. Distributed Transactions
 Private Workspace
 Writeahead Log
 Concurrency Control
 Serializability

Lahore Garrison University

 5
Introduction to Transactions

 Related to Mutual Exclusion, which protects a “shared resource”.

 Transactions protect “shared data”.
 Often, a single transaction contains a collection of
data accesses/modifications.
 The collection is treated as an “atomic operation” – either all the collection complete, or none of
them do.
 Mechanisms exist for the system to revert to a previously “good state” whenever a transaction
prematurely aborts.

Lahore Garrison University

 6
The Transaction Model

Lahore Garrison University

 Updating a master tape is fault tolerant.
 7
The Transaction Model (Cont.)

Primitive Description

BEGIN_TRANSACTION Make the start of a transaction

END_TRANSACTION Terminate the transaction and try to commit

ABORT_TRANSACTION Kill the transaction and restore the old values

READ Read data from a file, a table, or otherwise

WRITE Write data to a file, a table, or otherwise

Lahore Garrison University

 Examples of primitives for transactions.
 8
The Transaction Model (Cont.)

BEGIN_TRANSACTION BEGIN_TRANSACTION
reserve WP -> JFK; reserve WP -> JFK;
reserve JFK -> Nairobi; reserve JFK -> Nairobi;
reserve Nairobi -> Malindi; reserve Nairobi -> Malindi full =>
END_TRANSACTION ABORT_TRANSACTION
(a) (b)

a) Transaction to reserve three flights “commits”.

b) Transaction “aborts” when third flight is unavailable.

Lahore Garrison University

 9
A.C.I.D

 Four key transaction characteristics:

 Atomic: the transaction is considered to be one thing, even though it may be made up of many different
parts.
 Consistent: “invariants” that held before the transaction must also hold after its successful execution.
 Isolated: if multiple transactions run at the same time, they must not interfere with each other. To the
system, it should look like the two (or more) transactions are executed sequentially (i.e., that they are
serializable).
 Durable: Once a transaction commits, any changes are permanent.

Lahore Garrison University

 10
Types of Transactions

 Flat Transaction: this is the model that we have looked at so far. Disadvantage: too rigid. Partial
results cannot be committed. That is, the “atomic” nature of Flat Transactions can be a downside.
 Nested Transaction: a main, parent transaction spawns child sub-transactions to do the real work.
Disadvantage: problems result when a sub-transaction commits and then the parent aborts the main
transaction. Things get messy.
 Distributed Transaction: this is sub-transactions operating on distributed data stores. Disadvantage:
complex mechanisms required to lock the distributed data, as well as commit the entire transaction.

Lahore Garrison University

 11
Nested Transaction

Lahore Garrison University

 12
Nested vs. Distributed Transactions

 A distributed transaction – logically a flat, indivisible transaction that operates on

distributed data.
Lahore Garrison University
 13
Private Worskspace

a) The file index and disk blocks for a three-block

file
b) The situation after a transaction has modified
block 0 and appended block 3
c) After committing

Lahore Garrison University

 14
Write-ahead Log

x = 0; Log Log Log

y = 0;
BEGIN_TRANSACTION;
x = x + 1; [x = 0 / 1] [x = 0 / 1] [x = 0 / 1]
y=y+2 [y = 0/2] [y = 0/2]
x = y * y; [x = 1/4]
END_TRANSACTION;
(a) (b) (c) (d)

a) A transaction

Lahore Garrison University

b) – d) The log before each statement is executed
 15
Concurrency Control

General organization of managers for handling

transactions.

Lahore Garrison University

 16
Concurrency Control (Cont.)

General organization of managers for handling

distributed transactions.

Lahore Garrison University

 17
Serializability

BEGIN_TRANSACTION BEGIN_TRANSACTION BEGIN_TRANSACTION

x = 0; x = 0; x = 0;
x = x + 1; x = x + 2; x = x + 3;
END_TRANSACTION END_TRANSACTION END_TRANSACTION

(a) (b) (c)

Schedule 1 x = 0; x = x + 1; x = 0; x = x + 2; x = 0; x = x + 3 Legal
Schedule 2 x = 0; x = 0; x = x + 1; x = x + 2; x = 0; x = x + 3; Legal
Schedule 3 x = 0; x = 0; x = x + 1; x = 0; x = x + 2; x = x + 3; Illegal
(d)

a) – c) Three transactions T1, T2, and T3

Lahore Garrison University
d) Possible schedules
 18
Lesson Review

 Introduction to transactions
 The Transaction Model
 A.C.I.D
 Types of Transactions
 Nested Transactions vs. Distributed Transactions
 Private Workspace
 Writeahead Log
 Concurrency Control
 Serializability

Lahore Garrison University

 19
Next Lesson Preview

 Fault Tolerance Basic Concepts

 Dependability Basic Concepts
 Fault and Types of fault
 Failure Models
 Failure Masking by Redundancy
 Triple Modular Redundancy
 DS Fault Tolerance Topics
 Agreement in Faulty Systems

Lahore Garrison University

 20
References

 To cover this topic, different reference material has been used for consultation.

 Textbook:

Distributed Systems: Principles and Paradigms, A. S. Tanenbaum and M. V. Steen,

Prentice Hall, 2nd Edition, 2007.

Distributed and Cloud Computing: Clusters, Grids, Clouds, and the Future Internet, K.
Hwang, J. Dongarra and GC. C. Fox, Elsevier, 1st Ed.

 Google Search Engine

Lahore Garrison University