Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Distributed Deadlock?
3.
Three Approaches to Detect Deadlock in Distributed System
3.1.
Centralized Approach
3.2.
Distributed Approach
3.3.
Hierarchical Approach
4.
Deadlock Handling Strategies
5.
Types of Distributed Deadlock
5.1.
Resource Deadlock
5.2.
Communication Deadlock
6.
Issues In Deadlock Detection
7.
Resolution of Deadlock Detection
8.
Deadlock detection algorithms in Distributed System
8.1.
Path Pushing algorithms
8.2.
Edge Changing algorithms
8.3.
Diffusion computations Based algorithms
8.4.
Global state detection based algorithms
9.
Frequently Asked Questions
9.1.
What is a deadlock and how it is prevented in distributed systems?
9.2.
What is a false deadlock in a distributed database system?
9.3.
What is a deadlock in a distributed system and its types?
9.4.
What are the 3 alternatives for deadlock detection in distributed systems?
10.
Conclusion
Last Updated: Mar 27, 2024
Medium

Deadlock Detection in Distributed Systems

Author Kashish Saxena
2 upvotes
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM
deadlock in distributed system

Introduction

In distributed systems, it is nearly impossible to prevent deadlocks due to their vast areas of implementation. So, only deadlock detection is possible. Transactions or concurrency controls can lead to deadlocks in these systems. So, in this article, we will study Deadlock Detection in Distributed Systems.

Must Read - Multiprogramming vs Multitasking

What is Distributed Deadlock?

Deadlock in Distributed systems consists of multiple asynchronous processes. These processes communicate through message passing. Considering all processes are running on separate processors without loss of generality.

Deadlocks caused by communication delays between processes in Distributed Systems are known as Phantom Deadlocks. These deadlocks result in unnecessary process abortions.

The complexity of distributed systems makes deadlocks impossible to prevent. Therefore, detection is the only option. 

Deadlock detection techniques must have the following characteristics:

  1. Progress: All deadlocks in a system should be detected by a method that detects them. Essentially, the algorithm can detect a deadlock after all wait-for dependencies have been met. 
  2. Safety: Detection of false or phantom deadlocks should not be done by this method.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Three Approaches to Detect Deadlock in Distributed System

Here are some approaches to detect deadlock in distributed systems.

  • Centralized Approach
  • Distributed Approach
  • Hierarchical Approach

Centralized Approach

The advantage of the centralized approach is that it provides redundancy in detecting a deadlock, which protects the system from single-point failure. But it will result in high overhead because of extra messages for deadlock detection and recovery. Many nodes are responsible for detecting deadlock and trying to clear it.

Distributed Approach

Consider if a node detects a deadlock, the node's supervisor will be immediately notified. If some nodes have detected the same deadlock, they can report their supervisors to start the recovery operation. 

The distributed approach is better than the centralized one since it provides higher reliability and faster detection of deadlocks.

Hierarchical Approach

The best approach to deadlock detection in a distributed system is the combination of centralized and distributed techniques. This involves selecting specific nodes or clusters of nodes that are responsible for detecting deadlocks and having a single node control these chosen nodes.

Deadlock Handling Strategies

There are various deadlock handling strategies in the distributed system are as follows:

  1. Deadlock Prevention
  2. Deadlock Avoidance
  3. Deadlock Detection and Recovery

Types of Distributed Deadlock

There are mainly two types of distributed deadlock as follows:

Resource Deadlock

  • It happens when two or more processes wait indefinitely for each other to free resources for their tasks' completion, but it never happens on its own.
  • A process cannot be completed until it has all the required resources. Only when it has all the resources will it proceed toward completion. An AND condition can represent it.
  • Let us see an example of it in the below image:
resource deadlock
  • The above image shows that P1 has R1 and R2 but requires R3 for completion, which is assigned to P2, which requires R2 for completion, which P1 is holding. Also, P3 requires R3 but it is allocated to P2. Thus, this represents resource deadlock.

Communication Deadlock

  • It occurs when processes are waiting for some messages from other processes, which are further waiting from other processes in a cycle, and no message is being transmitted between them.
  • Since messages are not passed between processes, the processes wait indefinitely, and a deadlock occurs.
  • A Wait-For Graph can detect this to see which process requires a message from which function to resolve it further.
  • In this type, a process can move further if at least one resource is required. But in this case, a resource means a message from another process it needs to communicate with.
  • For two processes to progress, each one should be in an unblocked state.
  • An OR condition can represent this.
  • Let us see an example of it in the image below:
communication deadlock
  • Here, P1 requires to communicate with P2. P2 requires to communicate with P3. And P3 requires to communicate with P1. Thus no message passing is happening due to a state of deadlock.

Issues In Deadlock Detection

  • To detect deadlocks, it is necessary to take care of two issues at once: maintenance of the WFG and looking for cycles (or knots) within it. 
  • Detecting deadlocks and resolving them are two primary tasks of the deadlock handling approach that uses deadlock detection. 

Resolution of Deadlock Detection

  • To resolve deadlocks, existing wait-for dependencies must be broken between the processes. 
  • Rollback one or more blocked processes and assign their resources to the deadlocked processes so they can resume running.   

Deadlock detection algorithms in Distributed System

Resources can be requested in distributed systems in many ways using Knapps’ Classification Algorithms that are mentioned below:

  • Path Pushing Algorithms
  • Edge Changing Algorithms
  • Diffusing Computations Based Algorithms
  • Global State Detection Based Algorithms

Path Pushing algorithms

The central concept is to create a global WFG(wait-for graph) for each distributed system site. When a class of algorithms performs a deadlock computation, it sends its local WFG to all neighboring sites. 

When receiving the information from its neighbors, it performs the exact computation and sends back the obtained local WFGs. 

This process continues until all sites have obtained their local WFGs.

Edge Changing algorithms

This is a simple algorithm that can detect the presence of cycles in a distributed graph. There are two types of messages, request, and reply. A probe message is different from request and reply messages. Probe messages are short and fixed in size. 

The request message is sent from one site to another to obtain some desired resource, and that site sends a reply message to respond. 

If there is a cycle in the graph, the first site will receive the matching reply message by the second site through some other path (the second site is not directly connected to the first site). This is because of the existence of a cycle.

Diffusion computations Based algorithms

The detection problem can be solved using echo algorithms, first introduced by F. Baker and C. S. Dodds in the paper “Echo Algorithms for Distributed Deadlock Detection”. Echo algorithms use the notion of `echo' or `echoing back' a message received from other processes. The basic idea is to initiate an echo query and wait for the message.

Global state detection based algorithms

Deadlock detection algorithms use the following facts to detect the deadlock:

1) If a process has been waiting for another process, it can be said that the first process has a claim on the second one.

2)  If several processes have claims on each other, they form a cycle. Thus, they are mutually blocked.

This algorithm waits until a deadlock is detected. At that moment, it performs a snapshot of all the processes.

Frequently Asked Questions

What is a deadlock and how it is prevented in distributed systems?

A Deadlock is a state in which processes are in a blocked state because each one has some resources and is waiting for some other processes to free some resources. In Distributed systems, it is prevented by applying some constraints on the way in which processes ask for resources.

What is a false deadlock in a distributed database system?

False deadlock detection is the process of detecting an inexistent deadlock in distributed systems. According to this correspondence, a method of two-phase locking transactions will never encounter a false deadlock.

What is a deadlock in a distributed system and its types?

Deadlock in Distributed systems consists of multiple asynchronous processes. These processes communicate through message passing. Considering all processes are running on separate processors without loss of generality. There are two types of deadlock in a distributed system: resource and communication. 

What are the 3 alternatives for deadlock detection in distributed systems?

The three alternatives for deadlock detection in distributed systems are resource allocation graphs with centralized deadlock detection features, timeout-based deadlock algorithms involving specific periods for requests and permits, and a hierarchical approach for detection.

Conclusion

Let's take a look at what we have learned here:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of JavaScript, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Previous article
Program for Deadlock-free Condition
Next article
Difference between Deadlock and Starvation
Live masterclass