Distributed Computing

Proof for question 1 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. Let t be the first (earliest) such time. Since there were still messages in transit at t, consider the arrival times of these messages. Each of them arrives to its destination after the destination has sent its report to V. Consider the earliest such arrival time, i.e., the message from the messages that were in transit at t, 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. Since the accounting at V gave equality and did not account for M0’s arrival but did account for M0’s departure there must be another message M’ that arrives at k before the report that was sent from k to V (and was part of V’s equality at time t) and was sent from i to k after the corresponding report was sent from i to V. M0 has arrived at k at time t’, and was sent from i at t’’ (clearly t’’ < t’) and t’’ is after the report from i to V. M0 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, a contradiction to the assumption that t is the earliest arrival time of any message in transit when V reached equality.