  In applications of remote sensing, estimation, and control, timely
communication is not always ensured by high-rate communication. This work
proposes distributed age-efficient transmission policies for random access
channels with $M$ transmitters. In the first part of this work, we analyze the
age performance of stationary randomized policies by relating the problem of
finding age to the absorption time of a related Markov chain. In the second
part of this work, we propose the notion of \emph{age-gain} of a packet to
quantify how much the packet will reduce the instantaneous age of information
at the receiver side upon successful delivery. We then utilize this notion to
propose a transmission policy in which transmitters act in a distributed manner
based on the age-gain of their available packets. In particular, each
transmitter sends its latest packet only if its corresponding age-gain is
beyond a certain threshold which could be computed adaptively using the
collision feedback or found as a fixed value analytically in advance. Both
methods improve age of information significantly compared to the state of the
art. In the limit of large $M$, we prove that when the arrival rate is small
(below $\frac{1}{eM}$), slotted ALOHA-type algorithms are asymptotically
optimal. As the arrival rate increases beyond $\frac{1}{eM}$, while age
increases under slotted ALOHA, it decreases significantly under the proposed
age-based policies. For arrival rates $\theta$, $\theta=\frac{1}{o(M)}$, the
proposed algorithms provide a multiplicative factor of at least two compared to
the minimum age under slotted ALOHA (minimum over all arrival rates). We
conclude that, as opposed to the common practice, it is beneficial to increase
the sampling rate (and hence the arrival rate) and transmit packets selectively
based on their age-gain.
