Assume an asynchronous network with n nodes. Let the nodes' names be in the interval [1; n]. Let these two properties above be general knowledge.
There is shown a routing table at each node. (a) Suggest a distributed algorithm to confirm if the routing tables at nodes guarantee correct routing. The algorithm is needed to terminate explicitly, that is, every node is to finally enter a halting state while knowing whether the routing mechanism is correct or not. (b) Find the number of messages sent in the course of an execution, as a function of n.