Message Passing Architecture-Part Two

A number of possible problems can result from the use of certain routing mechanisms in message passing systems which include :Deadlock, Livelock, Starvation.
Deadlock
When two messages each hold the resources required by the other in order to move, both messages will be blocked. This is called a deadlock.
It is a phenomenon that occurs whenever there exists cyclic dependency for resources.
Management of resources in a network is the responsibility of the flow control mechanism used. Resources must be allocated in a manner that avoids deadlock.
A straightforward, but inefficient, way to solve the deadlock problem is to allow rerouting (maybe discarding) of the messages participating in a deadlock situation.
Rerouting of messages gives rise to nonminimal routing, while discarding messages requires that messages be recovered at the source and retransmitted.

A more common technique to avoid the occurrence of deadlock can be achieved by ordering network resources and requiring that messages request use of these resources in a strict monotonic order.
This restricted way for using network resources prevents the occurrence of circular wait, and hence prevents the occurrence of deadlock.
The Channel Dependency Graph (CDG) is a technique used to develop a deadlock-free routing algorithm.
CDG is a directed graph D = G(C, E), where the vertex set C consists of all the unidirectional channels in the network and the set of edges E includes all the pairs of connected channels, as defined by the routing algorithm.
In other words, if (ci, cj) E, then ci and cj are,respectively, an input channel and an output channel of a node and the routing algorithm may only route messages from ci to cj .
A routing algorithm is deadlock-free if there are no cycles in its CDG.
Consider, for example, the 4-node network shown in Figure below (a).
The CDG of the network is shown in Figure (b). There are two cycles
in the CDG and therefore this network is subject to deadlock.
Figure (c) shows one possible way to avoid the occurrence of deadlock, that is, disallowing messages to be forwarded from channel c1 to c2 and from c7 to c8