  There is a growing interest in analysing the freshness of data in networked
systems. Age of Information (AoI) has emerged as a popular metric to quantify
this freshness at a given destination. There has been a significant research
effort in optimizing this metric in communication and networking systems under
different settings. In contrast to previous works, we are interested in a
fundamental question, what is the minimum achievable AoI in any
single-server-single-source queuing system for a given service-time
distribution? To address this question, we study a problem of optimizing AoI
under service preemptions. Our main result is on the characterization of the
minimum achievable average peak AoI (PAoI). We obtain this result by showing
that a fixed-threshold policy is optimal in the set of all randomized-threshold
causal policies. We use the characterization to provide necessary and
sufficient conditions for the service-time distributions under which
preemptions are beneficial.
