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.
(i) 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? ?
(ii) When may a receiver remove a timestamp 175,000 (ms) from its table? (Hint: use the
receiver’s local clock value.)
(iii) Should the clocks be internally synchronized or externally synchronized?

What will be an ideal response?

i) If T ð T? then the message must be a repeat.
ii) 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.
iii) Internal synchronisation will suffice, since only time differences are relevant.