Distributed Computing

Proof for question 3 of the first homework:

Proof:

By way of contradiction, assume the two matrices are equal at node V at time t but there are still messages in transit in the network at t. For every node i, let t_i be the time at which node i sent the latest report to V which has arrived to V before time t (t_i = 0 if no report from node I reached V before time t). Since at time t there is still a message in transit in the network (by the contradiction assumption) then there must be a message M from some node j to some node h in the network, such that M was sent from j before t_j and M is received by h after t_h. From all such messages consider the message with the earliest such arrival time, i.e., the message from the messages that were in transit at [t_1, t_2, ..., t_i, ... t_j, ..., t_h,...t_n], with the smallest arrival time to its destination. Let M0 be this message that was sent from i to k and arrives at k at t0 (>t_k). Since the accounting at V gave equality and did not account for M0's arrival but did account for M0's departure (M0 was sent before t_j) there must be another message M' from i to k, that arrives at k before t_k, and was sent from i after t_i. M' has arrived at k at time t', and was sent from i at t'', clearly t' > t’’, and t'' > t_i (i.e., is after the report from i was sent to V). M' was sent from i at t'' only because there was another message that arrived at i at t'' (because it is an event driven algorithm). Thus a message in transit has arrived at node i at t'' < t' < t_k < t0, a contradiction to the assumption that t0 is the earliest arrival time of any message in transit at [t_1, t_2, ..., t_i, ... t_j, ..., t_h,...t_n]. QED