Timeliness in Through Telephones: Approximating Information Freshness in Vector Clock Models
Zoom: https://umd.zoom.us/j/6778156199?pwd=NkJKZG1Ib2Jxbmd5ZzNrVVlNMm91QT09
Friday, December 8, 2023, 10:00-11:00 am 
Abstract
Consider an information dissemination problem where the root of an undirected graph constantly updates its information. The goal is to keep every other node in the graph about the root as freshly informed as possible. This synchronous information spreading model uses telephone calls at each time step, in which any node can call at most one neighbor, thus forming a matching over which information is transmitted at each step. We introduce two problems in minimizing two natural objectives (Maximum and Average) of the latency of the root's information at all nodes in the network.
After deriving a simple reduction from the maximum rooted latency problem to the well-studied minimum broadcast time problem, we focus on the average rooted latency version. We introduce a natural problem of finding a finite schedule that minimizes the average broadcast time from a root. We show that any average rooted latency induces a solution to this average broadcast problem within a constant factor and conversely, this average broadcast time is within a logarithmic factor of the average rooted latency. Then, by approximating the average broadcast time problem via rounding a time-indexed linear programming relaxation, we obtain a logarithmic approximation to the average latency problem.
Surprisingly, we show that using the average broadcast time for average rooted latency introduces this necessary logarithmic factor overhead even in trees. We overcame this hurdle and give a 40-approximation for trees. This talk will highlight some of the techniques used to achieve these approximations and how they may be applied to other generalizations such as Multicommodity Multicast.
Bio
Da Qi Chen is a Postdoctoral Research Assistant in the Biocomplexity Institute at University of Virginia. He received his Ph.D. in Algorithms, Combinatorics and Optimization from Carnegie Mellon University. His research interests include Network Optimization, Approximation Algorithms and Extremal Graph Theory.
This talk is organized by Kishen N Gowda