The Dissemination of Time-Varying Information in Heterogeneous Network: A Delayed Reward

Abstract

In this paper, we conduct a performance analysis of a gossip network system designed to manage time-varying binary information, with a specific emphasis on scenarios where the strength of connections between nodes engaged in gossip exhibits heterogeneity. The communication system is consist of a single source from which information is updated and $n$ receiver nodes. When an update occurs, the source selects $m\le n$ nodes. After that, selected nodes disseminate update information during the \textit{gossiping period}. In the process, the source node focus on utilizing the gossiping between nodes, effectively deliver new updates to as many nodes as possible. By making sensible assumptions about system dynamics, system can be conceptualized as a Markov decision process (MDP). However, the derivation of an optimal policy becomes computationally intractable in the context of large-scale networks. To handle this challenge, we reinterpret the problem as a \textit{delayed reward} MDP (DRMDP) and conduct a comprehensive theoretical analysis to elucidate the interplay between system parameters critical for policy derivation. The DRMDP framework provides a scalable solution to navigate the complexities inherent in large-scale networks, offering a methodical approach to addressing the challenges posed by heterogeneous connection strengths. The proposed framework is substantiated through simulation results, affirming the efficacy of our approach. This work contributes to the formal understanding of gossip network coupled with heterogeneous connection and provides valuable insights into the derivation of scalable policies for the dissemination of time-varying information.