  Age-of-information (AoI) is a newly proposed performance metric of
information freshness. It differs from the traditional delay metric, because it
is destination centric and measures the time that elapsed since the last
received fresh information update was generated at the source. AoI has been
analyzed for several queueing models, and the problem of optimizing AoI over
arrival and service rates has been studied in the literature. We consider the
problem of minimizing AoI over the space of update generation and service time
distributions. In particular, we ask whether determinacy, i.e. periodic
generation of update packets and/or deterministic service, optimizes AoI. By
considering several queueing systems, we show that in certain settings,
deterministic service can in fact result in the worst case AoI, while a
heavy-tailed distributed service can yield the minimum AoI. This leads to an
interesting conclusion that, in some queueing systems, the service time
distribution that minimizes expected packet delay, or variance in packet delay
can, in fact, result in the worst case AoI. This exposes a fundamental
difference between AoI metrics and packet delay.
