2023/11/28 by Out, Charlotte, Rivera, Nicolás, Sauerwald, Thomas +1 · 1 citation
#05C85 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Parallel #Probability (math.PR) #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2311.17040
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.