233
views
0
recommends
+1 Recommend
1 collections
    0
    shares
       
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

      On Time Complexity of Distributed Algorithms for Generalized Deadlock Detection

      proceedings-article

      Proceedings of the First East-European Symposium on Advances in Databases and Information Systems (ADBIS)

      Advances in Databases and Information Systems

      2-5 September 1997

      Bookmark

            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 .

            Content

            Author and article information

            Conference
            September 1997
            September 1997
            : 1-16
            Affiliations
            [0001]Institute of Computing Science, Poznań University of Technology

            Poznań, Poland
            Article
            10.14236/ewic/ADBIS1997.8
            af25704f-5a85-479d-910a-ee9205363476
            © Jerzy Brzeziński et al. Published by BCS Learning and Development Ltd. Proceedings of the First East-European Symposium on Advances in Databases and Information Systems, (ADBIS'97), St Petersburg

            This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

            Proceedings of the First East-European Symposium on Advances in Databases and Information Systems
            ADBIS
            1
            St Petersburg
            2-5 September 1997
            Electronic Workshops in Computing (eWiC)
            Advances in Databases and Information Systems
            Product
            Product Information: 1477-9358BCS Learning & Development
            Self URI (journal page): https://ewic.bcs.org/
            Categories
            Electronic Workshops in Computing

            Comments

            Comment on this article