Blog
About

121
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 of the First East-European Symposium on Advances in Databases and Information Systems (ADBIS)

      Advances in Databases and Information Systems

      2-5 September 1997

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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.

          Related collections

          Most cited references 12

          • Record: found
          • Abstract: not found
          • Article: not found

          Distributed snapshots: determining global states of distributed systems

            Bookmark
            • Record: found
            • Abstract: not found
            • Conference Proceedings: not found

            Weighted voting for replicated data

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Some Deadlock Properties of Computer Systems

                Bookmark

                Author and article information

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

                Poznań, Poland
                Article
                10.14236/ewic/ADBIS1997.8
                © 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