COMPUTER SCIENCE AND ENGINEERING
End Semester Examination Pattern:
There will be two parts; Part A and Part B. Part A contains 10 questions with 2 questions from each
module, having 3 marks for each question. Students should answer all questions. Part B contains 2
full questions from each module of which student should answer any one. Each question can have
maximum 2 sub-divisions and carries 14 marks.
Syllabus
Module – 1 (Distributed systems basics and Computation model)
Distributed System – Definition, Relation to computer system components, Motivation, Primitives
for distributed communication, Design issues, Challenges and applications. A model of distributed
computations – Distributed program, Model of distributed executions, Models of communication
networks, Global state of a distributed system, Cuts of a distributed computation, Past and future
cones of an event, Models of process communications.
Module – 2 (Election algorithm, Global state and Termination detection)
Logical time – A framework for a system of logical clocks, Scalar time, Vector time. Leader election
algorithm – Bully algorithm, Ring algorithm. Global state and snapshot recording algorithms –
System model and definitions, Snapshot algorithm for FIFO channels – Chandy Lamport algorithm.
Termination detection – System model of a distributed computation, Termination detection using
distributed snapshots, Termination detection by weight throwing,Spanning-tree-based algorithm.
Module – 3 (Mutual exclusion and Deadlock detection)
Distributed mutual exclusion algorithms – System model, Requirements of mutual exclusion
algorithm. Lamport’s algorithm, Ricart–Agrawala algorithm, Quorum-based mutual exclusion
algorithms – Maekawa’s algorithm. Token-based algorithm – Suzuki–Kasami’s broadcast algorithm.
Deadlock detection in distributed systems – System model, Deadlock handling strategies, Issues in
deadlock detection, Models of deadlocks.
Module – 4 (Distributed shared memory and Failure recovery)
Distributed shared memory – Abstraction and advantages. Shared memory mutual exclusion –
Lamport’s bakery algorithm. Check pointing and rollback recovery – System model, consistent and
inconsistent states, different types of messages, Issues in failure recovery, checkpoint based
recovery, log based roll back recovery.
Module – 5 (Consensus and Distributed file system)
Consensus and agreement algorithms – Assumptions, The Byzantine agreement and other problems,
Agreement in (message-passing) synchronous systems with failures – Consensus algorithm for crash
Downloaded from Ktunotes.in
COMPUTER SCIENCE AND ENGINEERING
failures. Distributed file system – File service architecture, Case studies: Sun Network File System,
Andrew File System, Google File System.
(Note: Proof of correctness and performance analysis are not expected for any of the algorithms
in the syllabus).
Text Books
1. Ajay D. Kshemkalyani and Mukesh Singhal, Distributed Computing: Principles, Algorithms, and
Systems, Cambridge University Press, 2011.
Reference Books
1. George Coulouris, Jean Dollimore, Tim Kindberg and Gordon Blair. Distributed Systems:
Concepts and Design, Addison Wesley, Fifth edition.
2. Kai Hwang, Geoffrey C Fox, Jack J Dongarra, Distributed and Cloud Computing – From
Parallel Processing to the Internet of Things, Morgan Kaufmann Publishers, 2012.
3. Sukumar Ghosh, Distributed Systems: An Algorithmic Approach, CRC Press, Second edition,
2015.
4. Maarten Van Steen, Andrew S. Tanenbaum, Distributed Systems, Prentice Hall of India,Third
edition, 2017.
5. Randy Chow and Theodore Johnson, Distributed Operating Systems and Algorithm Analysis,
Pearson Education India, First edition, 2009.
6. Valmir C. Barbosa, An Introduction to Distributed Algorithms, MIT Press, 2003.
Course Level Assessment Questions
Course Outcome1 (CO1):
1. Define logical clock and explain the implementation of the logical clock.
2. Explain different forms of load balancing.
Course Outcome 2(CO2):
1. Apply ring-based leader election algorithm with 10 processes in the worst-performing case.
Count the number of messages needed.
2. Apply spanning tree-based termination detection algorithm in the following scenario. The
nodes are processes 0 to 6. Leaf nodes 3, 4, 5, and 6 are each given tokens T3, T4, T5 and T6
respectively. Leaf nodes 3, 4, 5 and 6 terminate in the order, but before terminating node 5,it
sends a message to node 1.
Downloaded from Ktunotes.in
