LIDS Tea: When to Refresh Data

We consider the timing of updates sent from a source to a destination, e.g., for a monitoring application. Each update sent by the source is subject to a random amount of delay, or service time (e.g.  in the network or cloud). There is a nonnegative (not necessarily convex) penalty that increases with the age of the freshest update at the destination, that is, a penalty that increases with the staleness of data. We study the problem of when to generate and send the next update, given the history of service times, to minimize a time average expected penalty.  We reach the somewhat surprising conclusion that it is not always optimal to update at the maximum allowed rate. Under Markovian service times, finding the optimal policy corresponds to solving a constrained SMDP with an uncountable state-space. We show that a stationary deterministic policy solves the problem, and using this, show that the problem reduces to a stochastic convex optimization problem, to which an efficient solution is found. We thus characterize the optimal amount of delay that the sender artificially imposes before generating the next update.

About LIDS Tea: LIDS Tea talks are 20 minute long informal presentations for the purpose of sharing ideas and making others aware of some of the topics that may be of interest to the LIDS audience. If you are interested in presenting in the upcoming seminars, please email Marzieh Parandehgheibi or Yasin Yazicioglu.