On the progress of communication between two finite state machines

We consider the following problem concerning any two finite state machines M and N that exchange messages via two 1-directional channels. “Is there a positive integer K such that the communication between M and N over K-capacity channels is guaranteed to progress indefinitely?” The problem is shown to be undecidable in general. For a practical class of communicating machines, the problem is shown to be decidable, and the decidability algorithm is polynomial. We also discuss some sufficient conditions for the problem to have a positive answer; these sufficient conditions can be checked for the given M and N in polynomial time. We apply the results to some practical protocols to show that their communications will progress indefinitely