APPENDIX A

Formal Definitions for Deadlock Avoidance

In this appendix we present a formal definition of most of the concepts defined in Section 3.1. These definitions are mainly based on [97]. This theory proposes a necessary and sufficient condition for an adaptive routing function to be deadlock-free. It is valid for networks using wormhole switching and routing functions that only consider the current and destination nodes in their domain.

The domain of the routing function can be extended by considering the input buffer containing the message header. This extension considerably changes the definitions. These changes can be found in [98], where a necessary and sufficient condition for deadlock avoidance is proposed for VCT and SAF switching. ...

Get Interconnection Networks now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.