A first storage system sends a clock synchronization message to a second storage system. The first storage system records a first value of a local time in the first storage system in conjunction with sending the clock synchronization message, and records a second value of the local time in the first storage system in conjunction with receipt of a response to the clock synchronization message from the second storage system. The response comprises a value of a local time in the second storage system. The first storage system computes an estimate of a difference between the local times using the recorded first and second values of the local time in the first storage system and the received value of the local time in the second storage system, and synchronizes the local time in the first storage system with the local time in the second storage using the computed estimate.