Deadlock detection in distributed systems

1. Deadlock Detection in Distributed Systems Dr. Davarpanah Research: Kaywan Zayer Reza Ramezani Mohammad Khosravi

2. Deadlock Introduction Strategies to handle deadlock Ostrich algorithm (ignore it) Detection (let occur, detect, recover) Prevention (make it impossible to o ccur) Avoidance (careful resource allocation)

3. Deadlock Detection Centralized Single point of failure bottleneck Distributed Soojung Lee Monjurul Alom et al Farajzadeh et al

4. Introduction Process dependency wait-for graph (WFG) Request model AND OR p out-of q Communication model Just message communication Bounded delay, reliable protocol

5. Soojung Lee Dependency Model Reduced wait-for graph (RWFG) knot Request model OR Blocked process can participate in deadlock detection algorithm

6. Message Probe Distributed Spanning Tree (DST) Path-string decoding Unique id Reply ACTIVE REPORT

7. Example (i) WFG (ii) DST

8. Example (iii) RWFG after receive ACTIVE (iv) RWFG after receive REPORT (v) Final RWFG

9. Monjurul Alom et al Distributed Database System Dependency model Transaction wait-for graph (TWFG) Request model AND Linear Transaction Structure (LTS) Distributed Transaction Structure (DTS)

10. Algorithm Scheme • LTS for each local site • DTS for global resource transaction communication • Priority Id for each transaction in each of the sites • The local and global cycles • Abort of the victim transaction based on the cycles

11. Example TWFG

12. Example LTS2 : {3->5, 5->6, 6->3} {7->10, 10->9, 9 -> 7 } {10->9, 9->11, 11->10} LTS3 :

13. Example

14. Example DTS1 : {4-> 3 , 3 -> 3 , 3 ->4, 4->4} DTS2 : {6-> 4 , 4 -> 8 , 8 ->7, 7->6}

15. Detected deadlock, breaking it

16. Final TWFG

17. Farajzadeh et al History-based edge chasing Probe message Request model p out-of q Messages Probe Clean-up Ok Deny

18. Algorithm Receive probe In memory and id = received id Prefix of received route-string deadlock Otherwise Save probe with smaller path-string and propagate received probe Deadlock Initiator Clean-up and suicide Otherwise Request permission for suicide

19. Comparison First an third algorithm Both use probe messages Build WFG Different in message number, delay, message size and resolution scheme Sujung lee farajzadeh Number of message 2e <=e Message size d+2 <=O(d) delay O( dlogn ) n resolutaion yes Yes, 2 message e : number of edge in WFG, n : number of node, d : diameter of WFG