A deadlock free and starvation free network of packet switching communication processors (Q1116325)

A network of communication processors is proved to be free of deadlock and starvation. The proof, given in detail, consists of two parts: the first part concerns the network, the second part concerns the communication processors. The proof is not, as many such proofs are, in the form of a reductio ad absurdum (derivation of a contradiction from the assumption that there is deadlock); instead, the proof is constructive: it is proved that there is guaranteed progress for every packet in the network.