Enhancement and Robustness of Large Timely Gossip Networks

Abstract

In this thesis, we explore the subject of fast dissemination of real-time data from a source to multiple users, critical for time-sensitive applications such as autonomous driving sytems, internet of things (IoT), augmented reality (AR), virtual reality (VR), and real-time content sharing in social networks, that feature dense interconnected networks of devices and humans. In face of network resource limitations and increasingly dynamic data generated by various sources in these networks, it is imperative that all nodes within these networks have timely information, i.e., the latest possible updates about the source nodes at all times for seamless functioning of these networks. Although it might seem straightforward to transmit changing data at high speed to all users, practical challenges such as limited bandwidth, server servicing speed, and intermittent connectivity hinder this approach. Therefore, to achieve the goal of timeliness, measured by metrics such as the age of information, this thesis leverages gossip algorithms, which are decentralized algorithms whose popularity stems from their efficiency and scalablility for information dissemination in such constrained and uncertain networks. This thesis aims to deepen our understanding of the capabilities and limitations of timely gossip networks of various topologies in managing large volumes of dynamic data. As importantly, this thesis explores the unique threats and vulnerabilities these next-generation networks face in the evolving landscape of 5G and 6G technologies. We open our analysis of this subject by first exploring efficient strategies for timely dissemination of time-varying data files from a source to a user via a simple network of parallel relays. We find that consolidating file update rates to the minimum number of relays improves timeliness, contrary to using all relays for each file. By solving an auxiliary single-cache problem and adapting its solution to our multi-cache network, we provide a sub-optimal solution, such that the upper bound on its gap to the optimal policy is independent of the number of files. Next, we explore complex network topologies and examine the resilience of gossip networks as a function of their connectivity to jamming attacks. We analyze the average version age in the presence of $\tilde{n}$ jammers for both connectivity-constrained ring and connectivity-rich fully connected topologies of $n$ nodes. Our findings reveal that a ring network is robust against up to $\sqrt{n}$ jammers, while a fully connected network withstands $n\log{n}$ jammers, showing that higher connectivity enhances resilience to jamming. To maximize age deterioration in the network, the jammers should attack in a manner that consolidates all remaining unjammed links into a dense cluster of the fewest possible nodes, leaving a higher number of nodes isolated. Next, we uncover a new type of attack in age-based networks, called timestomping, where an adversary manipulates timestamps of information packets, causing nodes to discard fresh packets for stale ones. We show that in fully connected networks, a single infected node can increase the expected age from $O(\log n)$ to $O(n)$, highlighting how full connectivity can expedite adversarial impacts. Conversely, in unidirectional ring networks with sparse inter-node connectivity, we find that the adversarial impact on node age scaling is confined by its distance from the adversary, maintaining an age scaling of $O(\sqrt{n})$ for a significant fraction of the network. Then, we demonstrate how the age-specific nature of file exchange protocols also makes gossip networks susceptible to the propagation of misinformation. We consider networks where packets can potentially get mutated during inter-node gossiping, creating misinformation. Nodes prefer latest versions of information, however, when a receiving node encounters both accurate information and misinformation for the same version, we consider two models: one where truth prevails over misinformation and another where misinformation prevails over truth. Using stochastic hybrid systems (SHS) modeling, we examine the expected fraction of nodes with correct information and the version age. We show that higher or lower gossiping rates effectively reduce misinformation when truth prevails, whereas moderate rates increase its spread. Conversely, misinformation prevalence rises with increased gossiping under the misinformation-prevailing scenario. Then, we consider the balance between freshness and reliability of information in an age-based gossip network, where two sources (reliable and unreliable) disseminate updates to $n$ network nodes. Nodes wish to have fresh information, however, they have preference for packets that originate at the reliable source and are willing to sacrifice their version age of information by up to $G$ versions to switch from an unreliable packet to a reliable packet. We show that increasing $G$ reduces unreliable packets but raises the network version age, revealing a freshness-reliability trade-off. Next, we develop a theory of timeliness for non-Poisson updating and study cache-aided networks where the inter-update times on the links are not necessarily exponentially distributed. We characterize the expressions for instantaneous age and version age in arbitrary networks, then derive their closed form expressions in case of tree networks, where they exhibit an additive structure. Finally, we analyze age of information in networks where update processes on the links become sparse as network size increases, noting that in symmetric fully connected networks, expected age scales as $O(\log{n})$. Then, we study a system where a group of users, interested in closely tracking a time-varying event and maintaining their expected version ages below a threshold, choose between either preferably relying on gossip from their neighbors or directly subscribing to a server publishing about the event, to meet the timeliness requirements. The server wishes to maximize its profit by boosting subscriptions from users and minimizing event sampling frequency to reduce costs, setting up a Stackelberg game between the server and the users. We analyze equilibrium strategies in both directed and undirected networks, finding that well-connected networks have fewer subscribers since well-connected users dissuade their multiple neighboring nodes from subscribing. Next, we consider a gossip network of $n$ users hosting a library of files, such that each file is initially present at exactly one node, designated as the file source. The source gets updated with newer versions of the file according to an arbitrary distribution in real-time, and the other users in the network wish to acquire the latest possible version of the file. We present a class of gossip protocols that achieve $O(1)$ age at a typical node in a single-file system and $O(n)$ age at a typical node for a given file in an $n$-file system. We show that file slicing and network coding based protocols fall under the presented class of protocols. Finally, we further explore timestomping attacks in a simplified communication model, where a source attempts to minimize the age of a user, but due to a power constraint, the source can only transmit updates directly to the user for a fraction of timeslots over a fixed time horizon. A cache node, which can afford more frequent transmissions, lies in between the source and the user, however the communication link between the cache and the user is under attack by a timestomping adversary. We formulate this adversarial cache updating problem as an online learning problem and study the achievable competitive ratios for this problem.