A scheme for implementing at-most-once reliable message delivery uses synchronized clocks to reject duplicate messages. Processes place their local clock value (a ‘timestamp’) in the messages they send. Each receiver keeps a table giving, for each sending process, the largest message timestamp it has seen. Assume that clocks are synchronized to within 100 ms, and that messages can arrive at most 50 ms after transmission.

a) When may a process ignore a message bearing a timestamp T, if it has recorded the last message received from that process as having timestamp T ?

b) When may a receiver remove a timestamp 175,000 (ms) from its table? (Hint: use the
receiver’s local clock value.)

c) Should the clocks be internally synchronized or externally synchronized?

a) If T ð T then the message must be a repeat.

b) The earliest message timestamp that could still arrive when the receiver’s clock is r is r - 100 - 50. If this is to be at least 175,000 (so that we cannot mistakenly receive a duplicate), we need r -150 = 175,000, i.e. r = 175,150.

c) Internal synchronisation will suffice, since only time differences are relevant.