Department of Computer Science and Engineering

AY 2023-24 IV Year VII Sem. CAT-2

CS3551 – DISTRIBUTED COMPUTING
KEY - ANSWER

PART-A

1. What are the requirements of Mutual Algorithm?

Mutual exclusion algorithms ensure that if a process is already performing write operation on a data object no other
process/thread is allowed to access/modify the same object until the first process has finished writing upon the data object and
released the object for other processes to read and write upon.

2. State two types of messages in Ricart-Agarwala algorithm

The algorithm uses two types of messages: REQUEST and REPLY. A process sends a REQUEST message to all other processes
to request their permission to enter the critical section. A process sends a REPLY message to a process to give its permission to
that process.

3. List the deadlock handling strategies in Distributed system.

The deadlock handling strategies
 Deadlock Avoidance
 Deadlock Ignorance
 Deadlock Prevention
 Deadlock Detection

4. What are the uses of Rollback recovery?

Rollback recovery treats a distributed system application as a collection of processes that communicate over a network. It
achieves fault tolerance by periodically saving the state of a process during the failure-free execution, enabling it to restart from a
saved state upon a failure to reduce the amount of lost work.

5. Define consensus in distributed system

Consensus in a distributed system, then, is the notion that all of the nodes agree on a state variable's value. To be precise,
consensus is a property that may be achieved by protocols attempting to determine a variable's value.

6. State Byzantine agreement problem.

Byzantine agreement Problem in a Distributed System. Every processor has its own beginning value in the consensus issue, and
all non faulty processors must agree on a single common value.

7. Write the purpose of using checkpoints.

Checkpoints are used to ensure that the database can be recovered quickly in the event of a failure. This is important for databases
that are critical to the operation of a business, as it ensures that data is not lost in the event of a failure

PART - B

8.a.i. Explain requirement and performance metric of mutual exclusion

Requirements of Mutual exclusion Algorithm:
 No Deadlock: Two or more site should not endlessly wait for any message that will never arrive.
 No Starvation: Every site who wants to execute critical section should get an opportunity to execute it in finite time.
 Fairness: Each site should get a fair chance to execute critical section.
 Fault Tolerance: In case of failure, it should be able to recognize it by itself in order to continue functioning without any
disruption.
Solution to distributed mutual exclusion: . Below are the three approaches based on message passing to implement mutual
exclusion in distributed systems:
1. Token Based Algorithm:
A unique token is shared among all the sites.If a site possesses the unique token, it is allowed to enter its critical section. Each
requests for critical section contains a sequence number. This sequence number is used to distinguish old and current requests.
Example : Suzuki–Kasami Algorithm
2. Non-token based approach:
This approach use timestamps instead of sequence number to order requests for the critical section.
Whenever a site make request for critical section, it gets a timestamp. Timestamp is also used to resolve any conflict between
critical section requests. Example : Ricart–Agrawala Algorithm
3. Quorum based approach:
Instead of requesting permission to execute the critical section from all other sites, Each site requests only a subset of sites which is
called a quorum.Any two subsets of sites or Quorum contains a common site. Example : Maekawa’s Algorithm
8a..ii. Analyze deadlock detection and recovery in distributed system
Deadlock detection and recovery is the process of detecting and resolving deadlocks in an operating system. A deadlock occurs when
two or more processes are blocked, waiting for each other to release the resources they need.
Deadlock Detection :
 1. If resources have a single instance
In this case for Deadlock detection, we can run an algorithm to check for the cycle in the Resource Allocation Graph. The
presence of a cycle in the graph is a sufficient condition for deadlock.
In the above diagram, resource 1 and resource 2 have single instances. There is a cycle R1 → P1 → R2 → P2. So, Deadlock is
Confirmed.
2. If there are multiple instances of resources –
Detection of the cycle is necessary but not a sufficient condition for deadlock detection, in this case, the system may or may not be
in deadlock varies according to different situations.
3. Wait-For Graph Algorithm –
The Wait-For Graph Algorithm is a deadlock detection algorithm used to detect deadlocks in a system where resources can have
multiple instances. The algorithm works by constructing a Wait-For Graph, which is a directed graph that represents the
dependencies between processes and resources.
Deadlock Recovery:
A traditional operating system such as Windows doesn’t deal with deadlock recovery as it is a
time and space-consuming process. Real-time operating systems use Deadlock recovery.
1. Killing the process –Killing all the processes involved in the deadlock. Killing process one
by one. After killing each process check for deadlock again and keep repeating the process
till the system recovers from deadlock. Killing all the processes one by one helps a system
to break circular wait conditions
2. Resource Preemption –Resources are preempted from the processes involved in the
deadlock, and preempted resources are allocated to other processes so that there is a
possibility of recovering the system from the deadlock. In this case, the system goes into
starvation.
3. Concurrency Control – Concurrency control mechanisms are used to prevent data
inconsistencies in systems with multiple concurrent processes.These mechanisms ensure
that concurrent processes do not access the same data at the same time, which can lead to
inconsistencies and errors. Concurrency control mechanisms can help prevent deadlocks by
managing access to shared resources and ensuring that concurrent processes do not interfere
with each other.

8.b.Explain Ricart Agarwala algorithm with example

The Ricart & Agrawala algorithm is a distributed mutual exclusion algorithm that allows multiple processes to access a shared
resource without conflicts. It ensures that only one process can access the resource at a time, while other processes wait for their
turn.
The algorithm works as follows:
 Each process maintains a local timestamp and a request queue to keep track of incoming requests.
 When a process wants to access the shared resource, it sends a request message to all other processes, including its local
timestamp.
 Upon receiving a request message, a process compares the timestamp of the requesting process with its own timestamp
and the timestamp of the process that currently holds the resource.
 If the requesting process has a lower timestamp and is not currently accessing the resource, the receiving process grants
permission by sending a reply message.
 If the requesting process has a higher timestamp or is currently accessing the resource, the receiving process adds the
request to its request queue and replies later when it releases the resource.
 Once a process receives replies from all other processes, it can enter the critical section and access the shared resource.
 After completing its task in the critical section, the process releases the resource and sends release messages to all
processes in its request queue.
 Upon receiving a release message, a process removes the corresponding request from its request queue and checks if it can
grant permission to any waiting process.
Example with 5 Processes
Let's consider an example with 5 processes: P1, P2, P3, P4, and P5.
 Initially, all processes have a local timestamp of 0 and empty request queues.
 Process P1 wants to access the shared resource and sends a request message to all other processes with its timestamp.
 Upon receiving the request, each process compares the timestamps and replies accordingly.
 P2, P3, P4, and P5 grant permission to P1 since their timestamps are higher.
 P1 receives replies from all other processes and enters the critical section to access the resource.
 After completing its task, P1 releases the resource and sends release messages to all processes in its request queue.
 P2, P3, P4, and P5 receive the release message and remove P1's request from their request queues.
 If any process has no pending requests in its queue, it can enter the critical section and access the resource.
This process continues as other processes request access to the resource, ensuring that only one process can access it at a time.
9.i. Describe Wait for Graph (WGF) with diagram
Wait-for-Graph Algorithm: It is a variant of the Resource Allocation graph. In this algorithm, we only have processes as vertices in
the graph. If the Wait-for-Graph contains a cycle then we can say the system is in a Deadlock state. Now we will discuss how the
Resource Allocation graph will be converted into Wait-for-Graph in an Algorithmic Approach. We need to remove resources while
converting from Resource Allocation Graph to Wait-for-Graph.
Consider a Resource Allocation Graph with 4 Processes P1, P2, P3, P4, and 4 Resources R1, R2, R3, R4. Find if there is a deadlock
in the Graph using the Wait for Graph-based deadlock detection algorithm.
Step 1: First take Process P1 which is waiting for Resource R1, resource R1 is acquired by Process P2, Start a Wait-for-Graph for
the above Resource Allocation Graph.
Step 2: Now we can observe that there is a path from P1 to P2 as P1 is waiting for R1 which is been acquired by P2. Now the Graph
would be after removing resource R1 looks like.
Step 3: From P2 we can observe a path from P2 to P3 as P2 is waiting for R4 which is acquired by P3. So make a path from P2 to
P3 after removing resource R4 looks like.
Step 4: From P3 we find a path to P4 as it is waiting for P3 which is acquired by P4. After removing R3 the graph looks like this.
Step 5: Here we can find Process P4 is waiting for R2 which is acquired by P1. So finally the Wait-for-Graph is as follows:
Step 6: Finally In this Graph, we found a cycle as the Process P4 again came back to the Process P1 which is the starting point (i.e.,
it’s a closed-loop). So, According to the Algorithm if we found a closed loop, then the system is in a deadlock state. So here we can
say the system is in a deadlock state.

9.ii..Discuss the issues of failure recovery with example

Checkpoints : {𝐶𝑖,0, 𝐶𝑖,1}, {𝐶𝑗,0, 𝐶𝑗,1, 𝐶𝑗,2}, and {𝐶𝑘,0, 𝐶𝑘,1, 𝐶𝑘,2} • Messages : A - J • The restored global consistent state :
{𝐶𝑖,1, 𝐶𝑗,1, 𝐶𝑘,1}

Issues in failure recovery • The rollback of process 𝑃𝑖 to checkpoint 𝐶𝑖,1 created an

orphan message H • Orphan message I is created due to the roll back of process 𝑃𝑗 to
checkpoint 𝐶𝑗,1 • Messages C, D, E, and F are potentially problematic – Message C: a

restored state for 𝑃𝑗 , but the receive event has been undone at process 𝑃𝑖 . – Lost
delayed message – Message D: a lost message since the send event for D is recorded in the

messages can be handled by having processes keep a message log of all the sent messages –
Messages E, F: delayed orphan messages. After resuming execution from their
checkpoints, processes will generate both of these messages

9.b. Name and explain the different types of deadlock models with neat diagram
MODELS OF DEADLOCKS.
AND model, a process can request more than one resource simultaneously and the request is satisfied only after all the requested
resources are granted to the process. The requested resources may exist at different locations The out degree of a node in the WFG
for AND model can be more than 1. The presence of a cycle in the WFG indicates a deadlock in the AND model. Each node of the
WFG in such a model is called an AND node. In the AND model, if a cycle is detected in the WFG, it implies a deadlock but not
vice versa. That is, a process may not be a part of a cycle, it can still be deadlocked.
OR Model A process can make a request for numerous resources simultaneously and the request is satisfied if any one of the
requested resources is granted. Presence of a cycle in the WFG of an OR model does not imply a deadlock in the OR model. In the
OR model, the presence of a knot indicates a deadlock.
Each of the process is the set S is blocked. The dependent set for each process in S is a subset of S. 3. No grant message is in transit
between any two processes in set S. A blocked process P is the set S becomes active only after receiving a grant message from a
process in its dependent set, which is a subset of S.
XOR Model This is a variation of AND-OR model. This allows a request to obtain any k available resources from a pool of n
resources. Both the models are the same in expressive power. This favors more compact formation of a request. Every request in
this model can be expressed in the AND-OR model and vice-versa. Note that AND requests for p resources can be stated as and OR
requests for p resources can be stated

10.a.i. Discuss Byzantine agreement problem

Byzantine Agreement Problem: The Byzantine agreement problem necessitates that a single value be agreed upon by all non-
faulty processors, with the initial value chosen by an arbitrarily chosen processor. The source processor broadcasts this initial value
to all other processors, and the solution must assure agreement on the same value among all non-faulty processors, with the
exception that if the source processor is not faulty, the agreed-upon value must match the source’s initial value. In the event that the
source processor is faulty, non-faulty processors can agree on any common value, regardless of what faulty processors agree on or
agree on at all.

10.a.ii. What is local checkpoint? Explain.

A local checkpoint is a snapshot of the state of the process at a given instance and the event of recording the state of a
process is called local check pointing. All processes save their local states at certain instants of time. A local check point is a
snapshot of the state of the process at a given instance
Assumption – A process stores all local checkpoints on the stable storage – A process is able to roll back to any of its existing local

𝐶𝑖, – The kth local checkpoint at process

checkpoints

,0 – A process 𝑃𝑖 takes a checkpoint

 𝐶𝑖,0 before it starts execution

10.b. Illustrate the different types of failures in distributed systems and explain how to prevent it.
Types of failure
1. System failure : The primary reason for a system failure is a software or hardware failure. It is a suitable assumption that a
system failure always results in the loss of the contents of the primary memory, while the secondary storage remains safe.
Whenever there is a system failure, the processor fails to perform the execution. During a system failure, the system may reboot or
freeze.
2. Communication medium failure : The main reason for a communication medium failure is the failure of the communication
link or the shifting of nodes. A possible scenario can be a website within a network that is trying to communicate with another
operational website within the network, but is unable to establish the connection.
3. Secondary storage failure : If the information stored on the secondary storage device is inaccessible, it is called a secondary
storage failure. Secondary storage failure can be caused by several reasons. Some of the common reasons are listed as follows:
 Node crash
 Dirt on the medium
 Parity error
4. Method failure : most often halts the distributed system. Moreover, it makes the system result in incorrect execution, or unable
to perform any execution at all. A system may enter a deadlock state or do protection violations during a method failure.