Vimal Jyothi Engineering College
(Autonomous)
DEPARTMENT OF
VIIIth Semester - [Link]
Course : CST402 - DISTRIBUTED COMPUTING
QNo QUESTION CO MARK
Module 2
Submodule 1
Topic 1
1. Define Lamport scalar time. CO2 (3.00)
( Theory ) ( Remembering(R) ) ( Easy )
2. List and explain the basic properties of vector time. CO2 (3.00)
( Theory ) ( Remembering(R) ) ( Easy )
3. Define the consistency property of scalar time. CO2 (3.00)
( Theory ) ( Remembering(R) ) ( Easy )
4. a) Explain the evolution of vector time with a suitable diagram.(7 Marks)
b) Consider the following scenario of electing the coordinator. Answer the following questions
assuming that the bully algorithm is used for the election process. (7 Marks)
i) What happens if 7 has not crashed? Who will it send a message to?
ii) Can 7 never initiate the election?
iii) When does a smaller ID process know it should start an election?
iv) In the above example what happens if 7 is recovered?
CO2 (14.00)
v) In the example, how will 7 see 6 is the coordinator (How does a process know who the
coordinator is)?
( Problem ) ( Applying(P) ) ( Hard )
5. a) Define properties of vector time. (7 Marks)
CO2 (14.00)
b) Explain the basic properties of scalar time. (7 Marks)
( Theory ) ( Remembering(R) ) ( Easy )
6. a) Differentiate between scalar time and vector time in the context of distributed systems. (7
Marks)
CO2 (14.00)
b) Discuss the attributes and operational guidelines necessary for the deployment of logical clocks
in a distributed environment. (7 Marks)
( Theory ) ( Understanding(U) ) ( Medium )
Submodule 2
Topic 1
1 of 4
7. Define the concept of leader election in a distributed system. Discuss the significance of having a
CO2 (3.00)
leader and the challenges involved in the process.
( Theory ) ( Understanding(U) ) ( Medium )
8. Illustrate the evolution of scalar time with an example. CO2 (3.00)
( Theory ) ( Understanding(U) ) ( Medium )
9. Explain the rules used to update clocks in scalar time representation. CO2 (3.00)
( Theory ) ( Understanding(U) ) ( Medium )
10. In a distributed system with processes P2, P5, P0, P3, P7, P1, P4, and P6, illustrate the Bully
algorithm. Assume P4 was the initial coordinator and crashed. If P3 initiates the election,
CO2 (14.00)
determine the total number of election messages and coordinator messages exchanged during the
execution of the algorithm.
( Problem ) ( Applying(P) ) ( Hard )
11. Illustrate bully algorithm for electing a new leader. Does the algorithm meet liveness and safety
CO2 (14.00)
conditions?
( Problem ) ( Applying(P) ) ( Medium )
12. Illustrate the Bully algorithm in a distributed system with processes P0, P4, P2, P1, P5, P6, P3,
and P7. If P7, the initial coordinator, crashes and P4 initiates the election, calculate the total
CO2 (14.00)
number of election messages and coordinator messages exchanged during the algorithm
execution.
( Problem ) ( Applying(P) ) ( Hard )
Submodule 3
Topic 1
13. What is the marker receiving rule? CO2 (3.00)
( Theory ) ( Remembering(R) ) ( Easy )
14. Explain marker sending rules. CO2 (3.00)
( Theory ) ( Remembering(R) ) ( Easy )
15. What are the necessary conditions to satisfy the consistent global state? CO2 (3.00)
( Theory ) ( Remembering(R) ) ( Easy )
16. In a ring topology 7 processes are connected with different ID’s as shown: P21->P4->P10->P19-
>P2->P16->P8 If process P4 initiates election after how many message passes will the coordinator
be elected and known to all the processes. What modification will take place to the election
CO2 (14.00)
message as it passes through all the processes? Calculate total number of election messages and
coordinator messages.
( Problem ) ( Applying(P) ) ( Hard )
17. Apply ring-based leader election algorithm with 10 processes in the worst-performing case. Count
CO2 (14.00)
the number of messages needed.
( Problem ) ( Applying(P) ) ( Hard )
18. Explain Ring based election algorithm in detail with an example. CO2 (14.00)
( Theory ) ( Understanding(U) ) ( Medium )
Submodule 4
Topic 1
2 of 4
19. Explain in detail how the markers flow through the channels and highlight when each process
records its local state in Snapshot algorithm. Also show which messages are "in transit" in the CO2 (14.00)
channels and how the states are combined to form the global state.
( Problem ) ( Understanding(U) ) ( Medium )
20. Define the system model and essential terms related to global state and snapshot recording in a
CO2 (3.00)
distributed system.
( Theory ) ( Remembering(R) ) ( Easy )
21. Explain the issues in recording a global state. CO2 (3.00)
( Theory ) ( Remembering(R) ) ( Easy )
22. What is meant by a consistent global state? CO2 (3.00)
( Theory ) ( Remembering(R) ) ( Easy )
23. a) Explain in detail about the Chandy Lamport algorithm. (6 Marks)
b) In the Chandy-Lamport algorithm for recording global snapshots, explain how the recorded
CO2 (14.00)
local snapshots can be put together to create the global snapshot. Can multiple processes initiate
the algorithm concurrently? (8 Marks)
( Theory ) ( Understanding(U) ) ( Medium )
24. a) Explain how the logical clock is implemented.(7 Marks)
CO2 (14.00)
b) Describe the capabilities and rules for implementation of logical clocks.(7 Marks)
( Theory ) ( Remembering(R) ) ( Easy )
Submodule 5
Topic 1
25. a) Clearly mentioning assumptions, explain the rules of termination detection using distributed
snapshots.(7 Marks)
b) Explain the rules for termination detection using distributed snapshots, explicitly stating the CO2 (14.00)
assumptions. Discuss how these rules ensure accurate termination detection in a distributed
system. (7 Marks)
( Problem ) ( Understanding(U) ) ( Medium )
26. Explain about termination detection. CO2 (3.00)
( Theory ) ( Understanding(U) ) ( Easy )
27. Identify consistent snapshot.
CO2 (3.00)
( Theory ) ( Remembering(R) ) ( Easy )
28. Sketch an interpretation in terms of cut for consistent global state. CO2 (3.00)
( Theory ) ( Understanding(U) ) ( Medium )
29. a) Explain the termination detection by weight throwing approach. Discuss how this method is
applied in a distributed system and how it helps in determining the termination of processes.(7
CO2 (14.00)
Marks)
b) Discuss the method of termination detection by weight throwing in detail. (7 Marks)
( Theory ) ( Understanding(U) ) ( Medium )
30. Explain the leader election algorithms in distributed systems with necessary diagrams and
CO2 (14.00)
examples.
( Theory ) ( Understanding(U) ) ( Medium )
Submodule 6
3 of 4
Topic 1
31. Explain the importance of spanning-tree-based algorithms in distributed systems. CO2 (3.00)
( Theory ) ( Understanding(U) ) ( Medium )
32. 'Scalar clocks can be used to totally order events in a distributed system'. Justify the statement
CO2 (3.00)
with a suitable example.
( Theory ) ( Understanding(U) ) ( Medium )
33. Define isomorphism property of scalar time. CO2 (3.00)
( Theory ) ( Remembering(R) ) ( Easy )
34. Illustrate the working of spanning tree-based termination detection algorithm with an example. CO2 (14.00)
( Theory ) ( Understanding(U) ) ( Medium )
35. 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
CO2 (14.00)
respectively. Leaf nodes 3, 4, 5 and 6 terminate in the order, but before terminating node 5,it sends
a message to node 1.
( Problem ) ( Applying(P) ) ( Hard )
36. Describe a spanning-tree-based algorithm used in distributed systems. Provide step-by-step
CO2 (14.00)
details and discuss how it helps in organizing communication and reducing redundancy.
( Theory ) ( Understanding(U) ) ( Medium )
4 of 4