Logical Clocks and Distributed System Protocols at IIT Kharagpur
Explore topics such as sliding window protocol, network routing, deadlock prevention, and logical clocks in distributed systems as presented in a series of questions from Indian Institute of Technology Kharagpur. Understand concepts like Lamport's logical timestamp and vector clock timestamps and their applications. Dive into the intricacies of distributed algorithms and system design.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Non-Distributed Excercises CS60002: Distributed Systems 1 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Sliding Window Protocol TRUE OR FALSE (with explanation) 1. In the sliding window protocol, we must use a large window size when the bandwidth of the communication channel is small. 2. In the sliding window protocol, a packet is never re-transmitted by process P after it has been received by the process Q. 2 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Network Routing TRUE OR FALSE (with explanation) 1. While the distributed version of the Floyd-Warshall algorithm is in execution, temporary cycles may be created in a routing path between some source and destination. 2. NetChange routing algorithm uses an upper-bound on the number of nodes to guarantee termination. 3 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Deadlock Prevention TRUE OR FALSE (with explanation) 1. Buffer graph for deadlock-free packet switching may have cycles if it has to support two-way communication between a pair of nodes. 2. Forward state controller for deadlock-free packet switching uses fewer buffers than a forward count controller. 4 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Logical Clocks With respect to the space-time diagram given below (where stars indicate local computation events), what would be the Lamport s logical timestamp and vector clock timestamp of the event a? a P1 P2 P3 5 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Logical Clocks With respect to the space-time diagram given below (where stars indicate local computation events), what would be the Lamport s logical timestamp and vector clock timestamp of the event a? 18 1 2 3 17 4 9 10 14 15 P1 2 1 6 5 11 12 9 10 7 14 P2 8 13 4 4 1 P3 10 5 4 15 16 LAMPORT S LOGICAL TIMESTAMP 6 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Logical Clocks With respect to the space-time diagram given below (where stars indicate local computation events), what would be the Lamport s logical timestamp and vector clock timestamp of the event a? [8,12,4] [2,0,0] [3,0,0] [7,12,4] [4,0,0] [6,7,0] [1,0,0] [5,7,0] [9,13,7] [10,13,7] P1 [0,1,0] [0,2,0] P2 [3,4,0] [3,5,0] [3,6,0] [3,9,4] [3,10,4][3,11,4] [3,13,4] [3,8,0] [3,12,4] [3,3,0] [3,7,0] P3 [0,0,1] [0,2,2] [0,2,3] [0,2,4] [3,8,5] [3,13,6] [3,13,7] VECTOR CLOCKS 7 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Suppose in Lamports Logical Clock, each node I increments its clock by a fixed positive constant di > 0 on an event (instead of incrementing by 1). Will the clocks work correctly if the di s are different for different i? Justify your answer. 8 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Global Snapshots Suppose that two processes i an j take five snapshots each of their local states independently at arbitrary times, with no communication for snapshot capture between them (i.e., no explicit snapshot capturing algorithm is run, processes just record their states whenever they want). Channel states are implicitly captured in the process states using message logs. Is it possible to have a scenario in which no pair of snapshots (one taken from i and one taken from j; there are 5*5=25 such pairs) is consistent? Justify your answer with a space-time diagram. 9 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Distributed Mutual Exclusion Show the following with an example using space-time diagrams involving two processes only: Why does Lamport s mutual exclusion algorithm require FIFO channels? Why Raicairol-Carvalho s mutual exclusion algorithm does not ensure timestamp- ordered entry into the critical section. 10 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
