A Local Deadlock Detection and Resolution Algorithm for Process Networks

Kahn Process Network (KPN) is a popular model for data streaming applications. Since it is impractical to implement an idealized KPN model with unbounded channel capacities, a bounded scheduling policy has been proposed by T. M. Parks. However, this policy would lead to artificial deadlocks in PN. Several deadlock detection mechanisms have been proposed to address this problem. In this paper, we propose an efficient deadlock detection algorithm which extends M. Prietopsilas algorithm for PN using message cooperation. It achieves a message complexity of O(n) and finds the bottleneck channel to resolve the artificial deadlock.