COURSE PLAN

Subject code: CS8603 Branch/Year/Sem/Section: B.E CSE/III/VI

Subject Name: Distributed Systems Batch:2017-2021
Staff Name: Dr.H.ABDUL SHABEER Academic year:2019-2020

COURSE OBJECTIVE

1. To understand the foundations of distributed systems.

2. To learn issues related to clock Synchronization and the need for global state in distributed systems.

3. To learn distributed mutual exclusion and deadlock detection algorithms.

4. To understand the significance of agreement, fault tolerance and recovery protocols in Distributed Systems.

5. To learn the characteristics of peer-to-peer and distributed shared memory systems

TEXT BOOK:
T1.Kshemkalyani, Ajay D., and Mukesh Singhal. Distributed computing: principles, algorithms, and systems. Cambridge
University Press, 2011
T2. George Coulouris, Jean Dollimore and Tim Kindberg, ―Distributed Systems Concepts and Design‖, Fifth Edition,
Pearson Education, 2012
REFERENCES:
R1. Pradeep K Sinha, “Distributed Operating Systems: Concepts and Design”, Prentice Hall of India, 2007 .
R2. Mukesh Singhal and Niranjan G. Shivaratri. Advanced concepts in operating systems. McGraw-Hill, Inc., 1994.
R3.Tanenbaum A.S., Van Steen M., ―Distributed Systems: Principles and Paradigms‖, Pearson Education, 2007
R4. Liu M.L., ―Distributed Computing, Principles and Applications‖, Pearson Education, 2004.
R5. Nancy A Lynch, ―Distributed Algorithms‖, Morgan Kaufman Publishers, USA, 2003.
WEB RESOURCES
W1: http://nptel.ac.in.
W2: http://www.cdk5.net/wp/references
TEACHING METHODOLOGIES:
 BB - BLACK BOARD
 VIDEO - VIDEO TUTORIAL
 PPT - POWER POINT PRESENTATION

DSIT/CSE/III YEAR/COURSE PLAN/CS8603-DS Page 1 of 9

 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

CS8603 DISTRIBUTED SYSTEMS LTPC 3003

UNIT I INTRODUCTION 9
Introduction: Definition –Relation to computer system components –Motivation –Relation to parallel
systems – Message-passing systems versus shared memory systems –Primitives for distributed
communication –Synchronous versus asynchronous executions –Design issues and challenges. A model of
distributed computations: A distributed program –A model of distributed executions –Models of
communication networks –Global state – Cuts –Past and future cones of an event –Models of process
communications. Logical Time: A framework for a system of logical clocks –Scalar time –Vector time –
Physical clock synchronization: NTP.
UNIT II MESSAGE ORDERING & SNAPSHOTS 9
Message ordering and group communication: Message ordering paradigms –Asynchronous execution
with synchronous communication –Synchronous program order on an asynchronous system –Group
communication – Causal order (CO) - Total order. Global state and snapshot recording algorithms:
Introduction –System model and definitions –Snapshot algorithms for FIFO channels
UNIT III DISTRIBUTED MUTEX & DEADLOCK 9
Distributed mutual exclusion algorithms: Introduction – Preliminaries – Lamport‘s algorithm – Ricart-
Agrawala algorithm – Maekawa‘s algorithm – Suzuki–Kasami‘s broadcast algorithm. Deadlock detection in
distributed systems: Introduction – System model – Preliminaries – Models of deadlocks – Knapp‘s
classification – Algorithms for the single resource model, the AND model and the OR model.
UNIT IV RECOVERY & CONSENSUS 9
Checkpointing and rollback recovery: Introduction – Background and definitions – Issues in failure
recovery – Checkpoint-based recovery – Log-based rollback recovery – Coordinated checkpointing algorithm
– Algorithm for asynchronous checkpointing and recovery. Consensus and agreement algorithms: Problem
definition – Overview of results – Agreement in a failure – free system – Agreement in synchronous systems
with failures.
UNIT V P2P & DISTRIBUTED SHARED MEMORY 9
Peer-to-peer computing and overlay graphs: Introduction – Data indexing and overlays – Chord – Content
addressable networks – Tapestry. Distributed shared memory: Abstraction and advantages – Memory
consistency models –Shared memory Mutual Exclusion.

DSIT/CSE/III YEAR/COURSE PLAN/CS8603-DS Page 2 of 9

1. At the end of the course, the student will be able to:

CO47.1 Elucidate the foundations and issues of distributed systems

CO47.2 Understand the various synchronization issues and global state for distributed systems.

CO47.3 Understand the Mutual Exclusion and Deadlock detection algorithms in distributed systems

CO47.4 Describe the agreement protocols and fault tolerance mechanisms in distributed systems.

CO 47.5 Describe the features of peer

2. Course Outcome (CO) Assessment:

Knowledge Internal Test

CO
Level 1 2 3

CO1 K2

CO2 K2

CO3 K2

CO4 K2

CO5 K3

CO6 K2

Cognitive Domain:
K1- Remember; K2- Understand; K3-Apply; K4- Analyse;K5- Evaluate; K6-Create

3. Programme Outcomes
Students graduating from Electrical and Electronics Engineering should be able to:

PO1 Engineering knowledge Strong foundation in core Computer Science and

Engineering, both theoretical and applied concepts
PO2 Problem analysis Identify, Formulate, Ability to apply knowledge of
mathematics, science and engineering to real-life problem
solving and reaching validated conclusions related to
computer science.
PO3 Design/development of Ability to analyze, design, model, and develop complex
solutions software and information management systems that meet
the specified needs with appropriate consideration for the
public health and Safety and the cultural societal and

DSIT/CSE/III YEAR/COURSE PLAN/CS8603-DS Page 3 of 9

 environmental considerations.
PO4 Conduct investigations of Ability to use research– based knowledge and study
complex problems methods including analysis, design , coding
implementation, testing and interpretation of data, to
provide valid Conclusions
PO5 Modern tool usage Convention of recent techniques, modern engineering and
IT tools with an understanding of the limitations
PO6 The engineer and society Apply Reasoning informed by the contextual knowledge to
assess societal, health, safety, legal and cultural issues and
the consequent responsibilities relevant to the Computer
Science and engineering Practice.

PO7 Environment and Understanding the impact of Computer Science and

sustainability Engineering solutions in the societal and human context.

PO8 Ethics Understand and apply professional ethical responsibility

PO9 Individual and team work Ability to function effectively within teams in Software
projects.
PO10 Communication Ability to communicate effectively, both in writing and oral
makes effective presentations to provide and obtain clear
instructions
PO11 Project management and Demonstrate knowledge and understanding of the
finance engineering management principles and apply these to
one’s own work, as a member and leader in a team, to
manage projects and in multi-disciplinary environments.

PO12 Life-long learning Recognize the need for and have the preparation and
ability to engage in independent and life-long learning.

4. Programme Specific Outcomes

After the successful completion of the U.G. programme in Computer Science and Engineering, Graduates will
be able to:
PSO1: Foundation of mathematical concepts: To use mathematical methodologies to crack problem
using suitable mathematical analysis, data structure and suitable algorithm.

PSO2: Foundation of Computer System: The ability to interpret the fundamental concepts,
methodology of computer systems and to understand the functionality of hardware and
software aspects.

PSO3: Foundations of Software development: The ability to grasp the software development
lifecycle and methodologies of software systems. Possess competent skills and knowledge of
software design process.

DSIT/CSE/III YEAR/COURSE PLAN/CS8603-DS Page 4 of 9

5. CO-PO Mapping Table:

COs PO PO PO PO PO PO PO PO PO PO PO PO PSO PSO PSO

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3
CO1 2 1 - - - - - - - - - - 2 - -
CO2 2 1 - - - - - - - - - - 3 - -
CO3 3 2 1 1 - - - - - - - - 3 2 2
CO4 3 2 1 1 - - - - - - - - 3 2 2
CO5 3 2 - - - - - - - - - - 3 2 2
Weighted
3 2 1 1 - - - - - - - - 3 2 2
average

TOTAL: 45 PERIODS
No of Cumulati
Topic Books For Teaching
Topic Name Page No periods ve
No reference Methodology
required periods
UNIT I INTRODUCTION (9)
Definition –Relation to
1. computer system components T1 1-4 BB 1 1
2. Motivation –Relation to parallel T1 13-21 BB 1 2
systems
Message-passing systems
versus shared memory systems
3. –Primitives for distributed T1 24-37 BB 1 3
communication
Synchronous versus
4. asynchronous executions – T1 37-48 BB 1 4
Design issues and challenges.
A distributed program ,A model
of distributed executions
5. T1 48-58 BB 1 5
,Models of communication
networks
Global state – Cuts –Past and
future cones of an event –
6. Models of process T1 58-67 BB 1 6
communications
A framework for a system of
7. logical clocks T1 68-77 BB 1 7

8. Scalar time –Vector time T1 78-84 BB 1 8

Physical clock synchronization:
9. NTP. T1 97-105 BB 1 9

DSIT/CSE/III YEAR/COURSE PLAN/CS8603-DS Page 5 of 9

LEARNING OUTCOME:
At the end of unit , the students will be able to
 Know the fundamentals of Distributed system.
 Understand the concept of message passing.
 Define the Distributed Computations.
UNIT II MESSAGE ORDERING & SNAPSHOTS (9)

1 Message ordering paradigms T1 121-127 BB 1 10

Asynchronous execution with

2 T1 128-135 BB 1 11
synchronous communication
Synchronous program order on
3 T1 136-142 BB 1 12
an asynchronous system

4 Group communication T1 143-152 BB 1 13

5 Causal order (CO) T1 153-160 BB 1 14

Global state and snapshot

6 recording algorithms: T1 171-180 BB 1 15
Introduction

7 System model and definitions T1 182-187 BB 1 16

8 Total order T1 188-195 BB 1 17

Snapshot algorithms for FIFO

9 T1 196-199 BB 1 18
channels
LEARNING OUTCOME:
At the end of unit , the students will be able to
 Understand the concept of message ordering
 Define Casual order
 Gain the knowledge about Snapshot

UNIT – III DISTRIBUTED MUTEX & DEADLOCK

(9) Distributed mutual exclusion
1 T1 205-209 BB 1 19
algorithms: Introduction
Preliminaries – Lamport‘s
2 T1 300-302 BB 1 20
algorithm
3 Ricart-Agrawala algorithm T1 303-305 BB 1 21
Maekawa‘s algorithm – Suzuki–
4 T1 306-308 BB 1 22
Kasami‘s broadcast algorithm.
Deadlock detection in
5 distributed T1 309-315 BB 1 23
systems:Introduction

DSIT/CSE/III YEAR/COURSE PLAN/CS8603-DS Page 6 of 9

 6 System model – Preliminaries T1 316-319 BB 1 24

Models of deadlocks – Knapp‘s

7 T1 320-328 BB 1 25
classification
Algorithms for the single
8 T1 329-335 BB 1 26
resource model
the AND model and the OR
9 T1 355-365 BB 1 27
model
LEARNING OUTCOME:
At the end of unit , the students will be able to
 Understand the concept of mutual algorithm.
 Gain knowledge about Deadlock.
 Define Distributed Mutex.
UNIT IV RECOVERY & CONSENSUS (9)
Checkpointing and rollback
1 T1 366-371 BB 1 28
recovery: Introduction
Background and definitions –
2 T1 371-375 BB 1 29
Issues in failure recovery
Checkpoint-based recovery – Log-
3 T1 376-384 BB 1 30
based rollback recovery
Coordinated checkpointing
4 T1 385-387 BB 1 31
algorithm
Algorithm for asynchronous W1
5 …. BB 1 32
checkpointing and recovery.

Consensus and agreement W1

6 …. BB 1 33
algorithms: Problem definition
7 Overview of results W1 …. BB 1 34
W1
8 Agreement in a failure …. BB 1 35

free system – 36
Agreement in
9 W1 …. BB 1
synchronous systems
with failures.
LEARNING OUTCOME:
At the end of unit , the students will be able to
 Understand the concept of failure recovery.
 Known about consensus.
UNIT V P2P & DISTRIBUTED SHARED MEMORY
(9) Peer-to-peer computing and
1 T1 402-410 BB 1 37
overlay graphs: Introduction
2 Data indexing and overlays T1 415-418 BB 1 38
3 Content addressable networks T1 419-425 BB 1 39

4 Tapestry. T1 426-430 BB 1 40

DSIT/CSE/III YEAR/COURSE PLAN/CS8603-DS Page 7 of 9

 5 Distributed shared memory W1 …. BB 1 41
6 Abstraction and advantages T1 452-460 BB 1 42
7 Memory consistency models W1 …. PPT 1 43

Shared memory Mutual

8 W2 …. PPT 1 44
Exclusion

9 Chord W1 …. PPT 1 45
LEARNING OUTCOME:
At the end of unit , the students will be able to
 Understand the concept of Distributed System.
 Known about P2P
 Gain knowledge about Distributed Shared memory

COURSE OUTCOME
 Understand the concept of Linux System
At the end of the course, the student should be able to:
 Know about the concept of Mobile OS - iOS and Android.
Elucidate the foundations and issues of distributed systems
 Understand the concept of Kernel Modules.
Understand the various synchronization issues and global state for distributed systems.
Understand the Mutual Exclusion and Deadlock detection algorithms in distributed systems
Describe the agreement protocols and fault tolerance mechanisms in distributed systems. Describe
the features of peer-to-peer and distributed shared memory systems
CONTENT BEYOND THE SYLLABUS
 Stream oriented Communication
 Hadoop Installation
CONTINUES INTERNAL ASSESSMENT DETAILS
ASSESMENT NUMBER I II MODEL
(UNIT) (1st & 2nd units) (3rd &4thunits) (units 1-5)

ASSIGNMENT DETAILS
ASSIGNMENT NUMBER I II III
TOPIC NUMBER FOR REFERENCE (1st & 2nd units) (3rd & 4th units) (units 1-5)
DEAD LINE

ASSIGNMENT BATCH DESCRIPTIVE QUESTIONS/TOPIC

NUMBER (Minimum of 8 Pages)
1. Explain in detail about Message passing system
2. Explain in detail about Models of communication
I 1
networks
3. Design issues and challenges
1. Ricart-Agrawala algorithm
II 1 2. Models of deadlocks
3. Distributed mutual exclusion algorithms

DSIT/CSE/III YEAR/COURSE PLAN/CS8603-DS Page 8 of 9

 1. Peer-to-peer computing
III 2. Consensus and agreement algorithms
1
3. Distributed shared memory

PREPARED BY VERIFIED BY

Mr.Dr.H.ABDUL SHABEER, AP/CSE HOD/CSE

APPROVED BY

PRINCIPAL

DSIT/CSE/III YEAR/COURSE PLAN/CS8603-DS Page 9 of 9