Self-stabilizing deadlock detection algorithms

ABSTRACT

A distributed system consists of a set of loosely connected state machines which do not share a global memory. All the possible global states of the system can be split up into legal and illegal states. A self-stabilizing system is a network of processors, which, when started from an arbitrary (and possibly illegal) initial state, always returns to a legal state in a finite number of steps. Self-stabilization has already been applied to some areas of distributed systems such as mutual exclusion, communication protocols, leader election, etc. [3][4]. This paper will present self-stabilizing deadlock detection algorithms, for single and multiple outstanding requests. Self-stabilizing methods for deadlock resolution and prevention are also discussed.

REFERENCES

• 1: K. Mani Chandy , Jayadev Misra , Laura M. Haas, Distributed deadlock detection, ACM Transactions on Computer Systems (TOCS), v.1 n.2, p.144-156, May 1983 [doi>10.1145/357360.357365]
• 2: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 3: M. Flatebo and A. Datta, "Self-Stabilizing Leader Election Algorithms," Twenty-ninth Annual Allerton Conference on Communication, Control, and Computing, Urbana, IL, October 2-4, 1991.
• 4: M. Flatebo, A. Dattn, and S. Ghosh, "Self- Stabilization in Distributed Systems," Advances in Distributed Computing: Concepts and Design, eds. T.L. Casavant and M. Singhal, IEEE Computer Society Press, 1992.
• 5: Edgar Knapp, Deadlock detection in distributed databases, ACM Computing Surveys (CSUR), v.19 n.4, p.303-328, Dec. 1987 [doi>10.1145/45075.46163]
• 6: M. Sfinghal, Deadlock Detection in Distributed Systems, Computer, v.22 n.11, p.37-48, November 1989 [doi>10.1109/2.43525]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Deadlocks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Theory