On necessary and sufficient conditions for deadlock-free routing in wormhole networks

F. Verbeek, J. Schmaltz

    Research output: Contribution to journalArticleAcademicpeer-review

    21 Citations (SciVal)


    Wormhole switching is a popular switching technique in interconnection networks. This technique is also prone to deadlocks. Adaptive routing algorithms provide alternative paths that can be used to escape congested areas and prevent some deadlocks to occur. If not designed carefully, these new paths may as well introduce deadlocks. A successful solution to deadlock prevention is to constrain the routing function such that it does not introduce any deadlock. Many necessary and sufficient conditions for deadlock-free routing have been proposed. The definition and the proof of these conditions are complex and error-prone. These conditions are often counterintuitive and difficult to understand. Moreover, they are not static, as they all require the analysis of configurations, i.e., the network state. The contribution of this paper is twofold. We present the first static necessary and sufficient condition for deadlock-free routing in wormhole networks. Our condition is much simpler and requires less assumptions than all previous ones. It is formally proven correct using an automated proof assistant. In particular, our condition applies to incoherent routing functions which was considered an open problem. Second, we prove the deadlock decision problem co-NP-complete for wormhole networks.
    Original languageEnglish
    Pages (from-to)2022-2032
    Number of pages11
    JournalIEEE Transactions on Parallel and Distributed Systems
    Issue number12
    Publication statusPublished - 2011


    Dive into the research topics of 'On necessary and sufficient conditions for deadlock-free routing in wormhole networks'. Together they form a unique fingerprint.

    Cite this