  In this paper, we consider a status updating system where the transmitter
sends status updates of the signal it monitors to the destination through a
rate-limited link. We consider the scenario where the status of the monitored
signal only changes at discrete time points. The objective is to let the
destination be synchronized with the source in a timely manner once a status
change happens. What complicates the problem is that the transmission takes
multiple time slots due to the link-rate constraint. Thus, the transmitter has
to decide to switch or to skip a new update when the status of the monitored
signal changes and it has not completed the transmission of the previous one
yet. We adopt a metric called "Age of Synchronization" (AoS) to measure the
"dissatisfaction" of the destination when it is desynchronized with the source.
Then, the objective of this paper is to minimize the time-average AoS by
designing optimal transmission policies for the transmitter. We formulate the
problem as a Markov decision process (MDP) and prove the multi-threshold
structure of the optimal policy. Based on that, we propose a low
computational-complexity algorithm for the MDP value iteration. We then
evaluate the performance of the multi-threshold policy through simulations and
compare it with two baseline policies and the AoI-optimal policy.
