We summarize recent contributions in the broad area of age of information (AoI). In particular, we describe the current state of the art in the design and optimization of low-latency cyberphysical systems and applications in which sources send time-stamped status updates to interested recipients. These applications desire status updates at the recipients to be as timely as possible; however, this is typically constrained by limited system resources. We describe AoI timeliness metrics and present general methods of AoI evaluation analysis that are applicable to a wide variety of sources and systems. Starting from elementary single-server queues, we apply these AoI methods to a range of increasingly complex systems, including energy harvesting sensors transmitting over noisy channels, parallel server systems, queueing networks, and various single-hop and multi-hop wireless networks. We also explore how update age is related to MMSE methods of sampling, estimation and control of stochastic processes. The paper concludes with a review of efforts to employ age optimization in cyberphysical applications.

We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of N non-colluding databases, each storing an MDS-coded version of M messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is C = (1 + K/N + K2/N2 +...+ KM−1/NM−1)−1 = (1 + Rc + Rc2 +...+ RcM−1)−1 = 1−Rc/1−RcM, where Rc is the rate of the (N,K) MDS code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost when the storage code is restricted to the class of MDS codes. The result generalizes the achievability and converse results for the classical PIR with replicated databases to the case of MDS-coded databases.

We consider the problem of single-round private information retrieval (PIR) from N replicated databases. We consider the case when B databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of M messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the T-privacy constraint in this paper, where any T databases can collude, and exchange the queries submitted by the user. We derive the information-theoretic capacity of this problem, which is the maximum number of correct symbols that can be retrieved privately (under the T-privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be C = N–2/N · 1– T/N–2B 1–( T/N–2B )M , if 2B + T < N. This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing 2B databases from the system, with a penalty factor of N–2B/N , which signifies that even though the number of databases needed for PIR is effectively N–2B, the user still needs to access the entire N databases. The result shows that for the unsynchronized PIR problem, if the user does not have any knowledge about the fraction of the messages that are mis-synchronized, the single-round capacity is the same as the BPIR capacity. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the errors introduced by the Byzantine databases as opposed to erasures in the RPIR problem. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes.

An energy-harvesting sensor node that is sending status updates to a destination is considered. The sensor is equipped with a battery of finite size to save its incoming energy, and consumes one unit of energy per status update transmission, which is delivered to the destination instantly over an error-free channel. The setting is online in which the harvested energy is revealed to the sensor causally over time after it arrives, and the goal is to design status update transmission times (policy) such that the long term average age of information (AoI) is minimized. The AoI is defined as the time elapsed since the latest update has reached at the destination. Two energy arrival models are considered: a random battery recharge (RBR) model, and an incremental battery recharge (IBR) model. In both models, energy arrives according to a Poisson process with unit rate, with values that completely fill up the battery in the RBR model, and with values that fill up the battery incrementally in a unit-by-unit fashion in the IBR model. The key approach to characterizing the optimal status update policy for both models is showing the optimality of renewal policies , in which the inter-update times follow a renewal process in a certain manner that depends on the energy arrival model and the battery size. It is then shown that the optimal renewal policy has an energy-dependent threshold structure, in which the sensor sends a status update only if the AoI grows above a certain threshold that depends on the energy available in its battery. For both the random and the incremental battery recharge models, the optimal energy-dependent thresholds are characterized explicitly , i.e., in closed-form, in terms of the optimal long term average AoI. It is also shown that the optimal thresholds are monotonically decreasing in the energy available in the battery, and that the smallest threshold, which comes in effect when the battery is full, is equal to the optimal long term average AoI.

A Gaussian MISO (multiple input single output) channel is considered where a transmitter is communicating to a receiver in the presence of an eavesdropper. The transmitter is equipped with multiple antennas, while the receiver and the eavesdropper each have a single antenna. The transmitter maximizes the communication rate, while concealing the message from the eavesdropper. The channel input is restricted to Gaussian signalling, with no preprocessing of information. For these channel inputs, and under different channel fading assumptions, optimal transmission strategies are found, in terms of the input covariance matrices. It is shown that, the optimal communication strategy in all cases, is beamforming.

We consider the problem of multi-message private information retrieval (MPIR) from N non-communicating replicated databases. In MPIR, the user is interested in retrieving P messages out of M stored messages without leaking the identity of the retrieved messages. The information-theoretic sum capacity of MPIR CsP is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol, where the symbols are defined over the same field. For the case P≥M/2, we determine the exact sum capacity of MPIR as CsP=1/1+M−P/PN. The achievable scheme in this case is based on downloading MDS-coded mixtures of all messages. For P≤M/2, we develop lower and upper bounds for all M,P,N. These bounds match if the total number of messages M is an integer multiple of the number of desired messages P, i.e., M/P ∈ N. In this case, CsP=(1+1/N+...+1/NM/P-1)-1, i.e., CsP=1-1/N/1-(1/N)M/P for N>1, and CsP=P/M for N=1. The achievable scheme in this case generalizes the single-message capacity achieving scheme to have unbalanced number of stages per round of download. For all the remaining cases, the difference between the lower and upper bound is at most 0.0082, which occurs for M=5, P=2, N=2. Our results indicate that joint retrieval of desired messages is more efficient than successive use of single-message retrieval schemes even after considering the free savings that result from downloading undesired symbols in each single-message retrieval round.