Proc. IEEE Conference on Acoustics, Speech, and Signal Processing, April 16-20, 2007, Honululu, HI USA, accepted for publication.

A Distributed Deadlock Detection and Resolution Algorithm for Process Networks

Gregory E. Allen, Paul E. Zucknick, and Brian L. Evans

Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX 78712 USA -

Paper - Slides

Software Release

Process Networks Research at UT Austin


In the Process Network (PN) model, multiple concurrent processes communicate over unidirectional FIFO queues. PN is useful for modeling signal processing systems of streaming data, and naturally captures parallelism in these systems. PN provides formal execution properties to alleviate the difficulties of threaded and distributed programming, and naturally maps onto parallel and distributed targets. For a large class of PN, clever run-time scheduling can permit execution in bounded memory. In general, PN termination and boundedness cannot be statically determined, so correct bounded scheduling of PN requires run-time deadlock detection. We present the first algorithm that correctly performs dynamic deadlock detection and resolution for bounded scheduling of PN. The proposed algorithm is a modification of a distributed deadlock detection algorithm by Mitchell and Merritt.

COPYRIGHT NOTICE: All the documents on this server have been submitted by their authors to scholarly journals or conferences as indicated, for the purpose of non-commercial dissemination of scientific work. The manuscripts are put on-line to facilitate this purpose. These manuscripts are copyrighted by the authors or the journals in which they were published. You may copy a manuscript for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect these copyrights.

Last Updated 12/12/12.