Abstract

Randomized rumor spreading processes diffuse information on an undirected graph and have been widely studied. In this work, we present a generic framework for analyzing a broad class of such processes on regular graphs. Our analysis is protocol-Agnostic, as it only requires the expected proportion of newly informed vertices in each round to be bounded, and a natural negative correlation property. This framework allows us to analyze various protocols, including PUSH, PULL, and PUSH-PULL, thereby extending prior research. Unlike previous work, our framework accommodates message failures at any time t ≥ 0 with a probability of 1-q(t), where the credibility q(t) is any function of time. This enables us to model real-world scenarios in which the transmissibility of rumors may fluctuate, as seen in the spread of "fake news" and viruses. Additionally, our framework is sufficiently broad to cover dynamic graphs.