A Distributed Deadlock Detection Algorithm and Its Correctness Proof.

Abstract

This paper presents a very simple distributed algorithm for deadlock detection in a network of processes. The algorithm is proven correct, i.e., we show that all true deadlocks are detected and no false reporting of deadlock occurs. In the algorithm no process maintains global information. All messages have identical length and are short, consisting of a single node name and a sequence number. Work is based on the work of Dijkstra and Scholten on termination detection of diffusing computations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1982
Accession Number
ADA120371

Entities

People

  • J. Misra
  • K. M. Chandy
  • L. Haas

Organizations

  • University of Texas at Austin

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Detection
  • Explosives Initiators
  • High Level Languages
  • Information Science
  • Language
  • Operating Systems
  • Programming Languages
  • Scientific Research
  • Sequences
  • Universities

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Database Systems and Applications