---
abstract: |-
  This is the appendix to the paper Load-Balanced Adaptive Routing for Torus Networks to provide a detailed, formal proof of the deadlock-freeness of the routing algorithm proposed in the paper. The paper is submitted to Electronics Letters, and the abstract of which is as follows:
   
  A new routing algorithm for torus interconnection networks to achieve high throughput on various traffic patterns, Adaptive Load-balanced routing with cycle Detection (ALD), is presented. Instead of the  -channels scheme adopted in a few recently proposed algorithms of the same category, a cycle detection scheme is employed in ALD to handle deadlock, which leads to higher routing adaptability. Simulation results demonstrate that ALD achieves higher throughput than the recently proposed algorithms on both benign and adversarial traffic patterns. 
altloc: []
chapter: ~
commentary: ~
commref: ~
confdates: ~
conference: ~
confloc: ~
contact_email: ~
creators_id: []
creators_name:
  - family: Wang
    given: Hong
    honourific: ''
    lineage: ''
  - family: Xu
    given: Du
    honourific: ''
    lineage: ''
  - family: Jiang
    given: Guo
    honourific: ''
    lineage: ''
  - family: Yao
    given: Yao
    honourific: ''
    lineage: ''
  - family: Xu
    given: Shizhong
    honourific: ''
    lineage: ''
  - family: Li
    given: Lemin
    honourific: ''
    lineage: ''
date: 2006-01
date_type: published
datestamp: 2006-01-14
department: ~
dir: disk0/00/00/47/01
edit_lock_since: ~
edit_lock_until: ~
edit_lock_user: ~
editors_id: []
editors_name: []
eprint_status: archive
eprintid: 4701
fileinfo: /style/images/fileicons/application_pdf.png;/4701/1/Deadlock.pdf
full_text_status: public
importid: ~
institution: ~
isbn: ~
ispublished: ~
issn: ~
item_issues_comment: []
item_issues_count: 0
item_issues_description: []
item_issues_id: []
item_issues_reported_by: []
item_issues_resolved_by: []
item_issues_status: []
item_issues_timestamp: []
item_issues_type: []
keywords: 'deadlock, routing algorithm, torus networks'
lastmod: 2011-03-11 08:56:19
latitude: ~
longitude: ~
metadata_visibility: show
note: ~
number: ~
pagerange: ~
pubdom: FALSE
publication: ~
publisher: ~
refereed: FALSE
referencetext: ~
relation_type: []
relation_uri: []
reportno: ~
rev_number: 12
series: ~
source: ~
status_changed: 2007-09-12 17:01:51
subjects:
  - comp-sci-mach-dynam-sys
succeeds: ~
suggestions: ~
sword_depositor: ~
sword_slug: ~
thesistype: ~
title: Proof of the deadlock-freeness of ALD routing algorithm
type: preprint
userid: 1180
volume: ~
<script src="//archive-bar.soton.ac.uk/archive-bar.js"></script>