On Time Complexity of Distributed Algorithms for Generalized Deadlock Detection.

@inproceedings{DBLP:conf/adbis/Brzezinski97,
  author    = {Jerzy Brzezinski},
  title     = {On Time Complexity of Distributed Algorithms for Generalized
               Deadlock Detection},
  booktitle = {Proceedings of the First East-European Symposium on Advances
               in Databases and Information Systems (ADBIS'97), St.-Petersburg,
               September 2-5, 1997. Volume 1: Regular Papers},
  publisher = {Nevsky Dialect},
  year      = {1997},
  pages     = {47-55},
  ee        = {db/conf/adbis/Brzezinski97.html},
  crossref  = {DBLP:conf/adbis/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Deadlock detection in distributed asynchronous systems - such as distributed database systems, computer networks, massively parallel systems etc. - is peculiarly subtle and complex. This is because asynchronous systems are characterized by the lack of global memory and a common physical clock, as well as by the absence of known bounds on relative processor speeds and transmission delays. These difficulties imply also problems with performance analysis of distributed algorithms for deadlock detection.

This paper deals with worst-case one-time complexity analysis of two well known distributed algorithms for generalized deadlock detection. The time complexity is expressed as a function of the diameter d and the longest path l of the wait-for-graph (WFG) characterizing a state of distributed system. First, the algorithm proposed by Bracha and Toueg is considered. It is shown that its time complexity is of 2d + 2l. Then, we prove that the time complexity of Kshemkalyani and Singhal algorithm is of (d + 1) + l.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-5 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

References

[1]

Gabriel Bracha, Sam Toueg: Distributed Deadlock Detection. Distributed Computing 2(3): 127-138(1987) BibTeX

[2]

...

[3]

...

[4]

K. Mani Chandy, Leslie Lamport: Distributed Snapshots: Determining Global States of Distributed Systems. ACM Trans. Comput. Syst. 3(1): 63-75(1985) BibTeX

[5]

K. Mani Chandy, Jayadev Misra: A Distributed Algorithm for Detecting Resource Deadlocks in Distributed Systems. PODC 1982: 157-164 BibTeX

[6]

K. Mani Chandy, Jayadev Misra, Laura M. Haas: Distributed Deadlock Detection. ACM Trans. Comput. Syst. 1(2): 144-156(1983) BibTeX

[7]

David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX

[8]

...

[9]

Richard C. Holt: Some Deadlock Properties of Computer Systems. ACM Comput. Surv. 4(3): 179-196(1972) BibTeX

[10]

...

[11]

Edgar Knapp: Deadlock Detection in Distributed Databases. ACM Comput. Surv. 19(4): 303-328(1987) BibTeX

[12]

Ajay D. Kshemkalyani, Mukesh Singhal: Efficient Detection and Resolution of Generalized Distributed Deadlocks. IEEE Trans. Software Eng. 20(1): 43-54(1994) BibTeX

[13]

...

[14]

Don P. Mitchell, Michael Merritt: A Distributed Algorithm for Deadlock Detection and Resolution. PODC 1984: 282-284 BibTeX

[15]

N. Natarajan: A Distributed Scheme for Detecting Communication Deadlocks. IEEE Trans. Software Eng. 12(4): 531-537(1986) BibTeX

[16]

Mukesh Singhal: Deadlock Detection in Distributed Systems. IEEE Computer 22(11): 37-48(1989) BibTeX

[17]

...