Exposure to Deadlock for Communicating Processes is Hard to Detect

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.