The complexity of reachability in distributed communicating processes


Journal Article

A crucial problem in the analysis of communicating processes is the detection of program statements that are unreachable due to communication deadlocks. In this paper, we consider the computational complexity of the reachability problem for various models of communicating processes. We obtain these models by making simplifying assumptions about the behavior of message queues and program control, with the hope that reachability may become easier to decide. Depending on the assumptions made, we show that reachability is undecidable, requires nearly exponential space infinitely often, or is NP-complete. In obtaining these results, we demonstrate a very close relationship between the decidable models and Petri nets and Habermann's path expressions, respectively. © 1988 Springer-Verlag.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Smolka, SA

Published Date

  • April 1, 1988

Published In

Volume / Issue

  • 25 / 3

Start / End Page

  • 333 - 354

Electronic International Standard Serial Number (EISSN)

  • 1432-0525

International Standard Serial Number (ISSN)

  • 0001-5903

Digital Object Identifier (DOI)

  • 10.1007/BF00283332

Citation Source

  • Scopus