Distributed Computing

Proof for question 1 of the first homework:

Proof:

By way of contradiction, assume the two matrices are

equal at node V but there are still messages in transit

in the network. Let t be the first time at which the matrices

are equal at V. Consider a node u:

from all the updates sent from

u to V and arrive at V no later than t, let the `latest’ one

be the one that was sent last from u.

Let t-u be the time at which the `latest’ update was sent

from u to V (if u did not send even one update to V,

then t-u is zero). Since, by the contradicting assumption,

there are still messages in transit, we can consider the

following set of messages:

{for each node u we consider the first message to arrive at u

after t-u}. From this set, consider the message, M-e, (for

M-earliest) to be the message that has arrived to its destination at

the earliest point in time (smallest time value), let this destination

be j, and the time at which M-e arrives at j be t-e. Message

M-e was sent from node i to node j. Since the matrices were

equal at V, and they did not include the arrival of M-e to j

(because M-e arrived at j after t-j) there must be another message

M-o (for M-other) that has arrived at j at t-a, before t-j but was

sent from i at t-s which is after t-i. Since node i sent the other

message,

M-o, at t-s it must have received a message at this point of time

too (nodes do not send messages out of the blue, but only in a response

to receiving a message). BUT, since a message is

sent before it arrives, t-s < t-a. But also, t-a < t-j < t-e.

But this is a contradiction since now t-s < t-e and M-e is not the

earliest message from the set above. Q.E.D.