MLR Institute of Technology (Autonomous)
DISTRIBUTED COMPUTING
IV [Link] - I SEMESTER
Course Code Category Hours/Week Credits Maximum Marks
L T P C CIE SEE Total
A6CS22 PCC
3 - - 3 40 60 100
COURSE OBJECTIVES
The course will enable the students to:
1. Understand the foundations of distributed systems.
2. Learn issues related to clock Synchronization and the need for global state in distributed systems
3. Learn distributed mutual exclusion and deadlock detection algorithms
4. Understand the significance of agreement, fault tolerance and recovery protocols in Distributed
Systems
5. Learn the characteristics of peer-to-peer and distributed shared memory systems
COURSE OUTCOMES
By the end of the course, the student will able to:
1. Elucidate the foundations and issues of distributed systems
2. Illustrate various synchronization issues and global state for distributed systems.
3. Illustrate Mutual Exclusion and Deadlock detection algorithms in distributed systems
4. Describe the agreement protocols and fault tolerance mechanisms in distributed systems
5. Describe the features of peer-to-peer and distributed shared memory systems.
UNIT - I A MODEL OF DISTRIBUTED COMPUTATIONS CLASSES: 12
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 CLASSES: 12
Global state and snapshot recording algorithms: Introduction, System model and definitions, Snapshot
algorithms for FIFO channels, Snapshot algorithms for non-FIFO channels,
Message Ordering & Snapshots: 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.
UNIT - III DISTRIBUTED MUTEX& DEADLOCK CLASSES: 12
Distributed Mutex& Deadlock: Distribut
algorithm, Ricart-
Deadlock detection in distributed systems: Introduction, System model, Preliminaries, Models of deadlocks,
[Link] Academic Regulations R22 Page 185
MLR Institute of Technology (Autonomous)
UNIT - IV RECOVERY & CONSENSUS CLASSES: 12
Recovery & Consensus: Check pointing and rollback recovery: Introduction, Background and definitions,
Issues in failure recovery, Checkpoint-based recovery, Log-based rollback recovery, Coordinated check
pointing algorithm, Algorithm for asynchronous check point in grand recovery.
Consensus and agreement algorithms: Problem definition, Overview of results, Agreement in a failure, free
system, Agreement in synchronous systems with failures.
UNIT - V PEER-TO-PEER COMPUTING AND OVERLAY GRAPHS CLASSES: 12
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.
TEXT BOOKS
1. Distributed computing: Principles, algorithms, and systems, Ajay Kshemkalyani and MukeshSinghal,
Cambridge University Press, 2011.
2. Distributed Systems Concepts and Design, George Coulouris, Jean Dollimore and Tim Kindberg, Fifth
Edition, Pearson Education, 2012.
REFERENCE BOOKS
1. Distributed Operating Systems: Concepts and Design, Pradeep K Sinha, Prentice Hall of India, 2007.
2. Advanced concepts in operating systems. MukeshSinghal and Niranjan G. Shivaratri, McGraw-Hill, 1994.
3. Java in Distributed Systems, Concurrency, Distribution and Persistence, Marko Boger, 2001.
4. Distributed Systems: Principles and Paradigms, Tanenbaum A.S., Van Steen M., Pearson Education,
2007.
5. Kshemkalyani Ajay D, Mukesh Singhal, Distributed Computing: Principles, Algorithms and Systems,
Cambridge Press, 2011
6. Mukesh Singhal, Niranjan G Shivaratri, Advanced Concepts in Operating systems, McGraw Hill
Publishers, 1994.
WEB LINKS
1. [Link]
2. [Link]
[Link] Academic Regulations R22 Page 186
