Age-of-information in distributed systems caused by asynchronous computing modeled as parallel renewal processes

Abstract We consider methods where processors from a distributed computing (DC) infrastructure compute updates for a set of parameters asynchronously. In such scenarios, the parameter updates can experience practically unbounded stochastic processing times caused by effects like queuing, processor sharing, priorities, preemption, or heavy-tailed traffic. As a result, processors will update parameters multiple times while one processor observes the parameters and calculates a new parameter update based on it. The resulting error between the current parameter and the older version used to calculate the parameter update is thus a function of a discrete information delay that we call Age-of-Information (AoI). To counter the errors caused by AoI, predict the performance of asynchronous algorithms, and effectively solve problems in machine learning and artificial intelligence, it is important to know AoI properties. To do this, we model the processing times in a DC system as parallel renewal processes. For this model, we derive the distribution and moment bounds for the discrete AoI affecting asynchronous algorithms executed on the DC system. We also derive exact expressions for the asymptotic mean and sharp bounds for the asymptotic variance.