Question 15: Fastest finger first
Saurabh is building a quizzing system for a school. Each student takes a quiz on their own machine. Once completed, the machine generates a timestamp and sends it along with the student's answers to a central server. The central server stores the answers and the timestamp. At a later point, answers for all the students are checked and the highest scoring student is declared to be the winner. In case of a tie (two or more students with the same score), the student who completed the quiz soonest wins. To determine that, Saurabh looks at the timestamp in the message.
Is Saurabh's implementation of finding the student who finished the quiz quickest correct?
Solution
Saurabh's implementation of finding the student who finished the quiz quickest is incorrect because the timestamp is generated on the student's machines. Time between any two machines is never guaranteed to be synchronized. Using unsynchronized clocks means that an earlier timestamp does not actually guarantee that the event actually happened before other events with a later timestamp (from a different clock).
One of the approaches that Saurabh can use is to generate a timestamp at the central server (because that would be coming from a single clock). However, this approach is susceptible to message delivery delays (messages from the students' machines to the central server).
In general, there is no way to know the ordering between two events that happen on two different machines in a distributed system without any sort of communication between the machines. Lamport's classic paper is an excellent read on this topic.