Consider the parallel traversal algorithm discussed in class, which is a more complete version of the algorithm in Fig. 1.4 of Raynal. We restate the algorithm below. Default assumptions that we assume in every algorithm, unless explicitly modified: --communication lines are error-free, i.e., any message sent on a line arrives, without any corruption, at the recipients input port within an arbitrary but finite time; and no messages are created by the system on its own. In other words, messages are not lost, corrupted, duplicated or created by the system on its own; and communication delays are arbitrary but finite. --Lines and input ports are FIFO. --Process speeds are arbitrary, but non-zero. --LHS of any rule is the reception of exactly one message Assumptions specifically made in this algorithm: --The lines and the input ports are non-FIFO i.e., messages do not necessarily arrive or are received in FIFO order. --The graph G representing the network is undirected (i.e., lines are bidirectional) and connected. --G has at least one node. --Initially there is a start() msg in transit to a particular process; we call this process the initiator (or I) --each node knows the set of its neighbors Desired Correctness Properties: Definition: At any moment, the system computation is said to be terminated, iff (a) there is no msg in transit or at an input port, and (b) each process is idle, i.e., it is not in the middle of executing a rule, i.e., either it is dead (e.g., by executing an exit statement) or it is at the point where it is next going to look for a ready rule. 1. Liveness: within a finite time, the system computation terminates, and 2. Safety: If the system computation is currently terminated, then by now each node has been visited exactly once. Notes: --here we are not requiring that termination is detected by a node. --The notion of visit has been discussed in class. The Pseudo Code for any process i: /*Initialization*/ bool visited=false; /* Rules*/ R1. On receiving start() visited = true; //we are officially visiting the node at this point. Send go() to each neighbor; //Note: it is possible to have no neighbors. R2. On receiving a go() from a neighbor j If (!visited) { visited=true; //we are officially visiting the node at this point. Send go() to each neighbor except j; } Questions for the HW: Each question suggests a modification to the above algorithm. For each question, say if the modified code works correctly. In case your answer is NO, then give a counter example and say which correctness property (or properties) is violated in this example. In case your answer is YES, then give an informal proof in less than 100 words. Q1. Suppose initially there are TWO start() messages, in transit to the same node I. Q2. Suppose initially there are TWO start msgs, each going to a different node (say I and A). Q3. Initially, there is no start() msg, but there is a go() msg in transit on the line from A to B. Q4. Exactly one go() msg at an input port gets duplicated, i.e., now there are two go() msgs instead. Q5. Exactly one go() msg in transit becomes a start() msg. Q6. Exactly one go() msg in transit gets lost.