Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6395
Title: Exposure to Deadlock for Communicating Processes is Hard to Detect
Authors: Raeuchle, Thomas
Toueg, Sam
Keywords: computer science
technical report
Issue Date: May-1983
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-555
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.
URI: http://hdl.handle.net/1813/6395
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
83-555.pdf407.96 kBAdobe PDFView/Open
83-555.ps154.92 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us