Age-Optimal Causal Labeling of Memoryless Processes

We consider a problem of labeling a memoryless temporal point process. The labelings have to be done causally. We study the tradeoff between the rate and age of the labeled process and characterize the optimal tradeoff curve. We show that the optimal curve can be achieved with rather simple labeling procedures which repeatedly do the following: Wait for T time units and label the next arrival.