Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
What is an example of an algorithm that requires synchronised clocks? Synchronised in an absolute sense, not just synchronised clock rates.
For more background, I've read Barbra Lisksov's 1993 paper 'Practical Uses of Synchronized Clocks in Distributed Systems' and also some content on Cloud Spanner and TrueTime. I'm still struggling to understand the advantages of using synchronised clocks on nodes in a distributed system.
I did some more thinking about this and I see at least one benefit of synchronized clocks, which is 'fairness when the topology is skewed'.
Imagine a situation with a server and two trusted clients. Eg. perhaps they're API servers in different data centers that end-users communicate with.
Server------------------------------Client A
\------Client B
Client A is much closer to the server than Client B.
Imagine that both clients send a message to purchase the last seat to a concert. Client A sends a request first and Client B sends a request shortly after.
Client A |A(send)
Client B |B(send)
Server |B(receive) |A(receive)
------------------------------------------------> time
The server received Client B's request before Clent A's. That is, the ordering seen by the server was different from the real-time ordering.
The real-time ordering is the order in which the events occurred in the physical world.
Client A may see this as unfair since they requested the ticket before Client B.
It's possible to maintain the real-time ordering of messages if each client has synchronized clocks in an absolute sense. That is, the clocks should have zero skew (and also zero drift).
If that's true then the server can preserve real-time ordering of events by 'waiting out' the uncertainty of both the clock skew and the network latency. The server will need to wait
$$t_{wait}=t_{max\_skew}+t_{max\_system\_latency}$$
from the time that the message was sent. That is, before processing a message the server has to wait as long as the maximum clock skew, plus the maximum one-way latency to the furthest client, minus the one-way latency of that message.
This approach assumes a synchronous system however it can be extended to work with the asynchronous timing model by making the server reject any message that was received more than $t_{wait}$ seconds after it was sent (the send time is in the message). In that case, the client would have to retry.
To summarise (TL;DR), synchronized clocks (with zero skew) can provide real-time ordering to a system. A concrete advantage of real-time ordering is that it's more 'fair' to participants when the network topology is skewed. The cost of real-time ordering with synchronized clocks is that the system has to 'wait out' the worst-case one-way latency and clock skew.
If you ask two systems "which happened first, A or B", and they give you the same answer, surely that's an advantage compared to getting two inconsistent answers.
On the other hand, what is the meaning of "synchronised clocks"? I would take it to mean "if I ask both clocks for the time at the same moment, I will get the same reply". But I can't ask two clocks at the same time; not if they are in different places. If I ask two clocks at almost the same moment, each can legitimately claim it is earlier in time. That's just physics.
The best method that I know is trying to get precise timing information from a clock, and then have a server who is the arbiter which events happened before which others, giving a total ordering to all events.
