Proc. IEEE Int. Conf. on
Acoustics, Speech, and Signal Proc.,
Mar. 19-23, 2005, vol. 5, pp. 73-76, Philadelphia, PA USA.
Deadlock Detection for Distributed Process Networks
Alex G. Olson
Brian L. Evans
Wireless Networking and
The University of Texas at Austin,
Austin, TX 78712 USA
Process Networks Research
at UT Austin
The Process Network (PN) model, which consists of concurrent processes
communicating over first-in first out unidirectional queues, is useful
for modeling and exploiting functional parallelism in streaming data
The PN model maps easily onto multi-processor and/or multi-threaded targets.
Since the PN model is Turing complete, memory requirements cannot be
In general, any bounded memory scheduling algorithm for this model
requires run-time deadlock detection.
The few PN implementations that perform deadlock detection detect only
Not all local deadlocks, however, will cause a PN system to reach global
In this paper, we present the first local deadlock detection algorithm
for PN models.
The proposed algorithm is based on the Mitchell and Merritt algorithm
and is suitable for both parallel and distributed PN implementations.
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
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
Last Updated 11/03/05.