JavaScript is disabled for your browser. Some features of this site may not work without it.
Exposure to Deadlock for Communicating Processes is Hard to Detect

Author
Raeuchle, Thomas; Toueg, Sam
Abstract
It is shown that the applicability of global state analysis as a tool for proving correctness of communication protocols is rather limited. Brand, et al. showed that reachability of global deadlock states for protocols with unbounded FIFO channels is undecidable. It is shown, that the same is true for unbounded non-FIFO channels. For bounded FIFO channels the problem is shown to be PSPACE-hard. Protocols with bounded non-FIFO channels are shown to be analyzable in polynomial time.
Date Issued
1983-05Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-555
Type
technical report