Asymptotics for push on the complete graph

Daknama, Rami; Panagiotou, Konstantinos und Reisser, Simon (2021): Asymptotics for push on the complete graph. In: Stochastic Processes and Their Applications, Bd. 137: S. 35-61

Abstract

We study the classical randomized rumour spreading protocol push. Initially, a node in a graph possesses some information, which is then spread in a round based manner. In each round, each informed node chooses uniformly at random one of its neighbours and passes the information to it. The central quantity of interest is the runtime, that is, the number of rounds needed until every node has received the information. The push protocol and variations of it have been studied extensively. Here we study the case where the underlying graph is complete with n nodes. Even in this most basic setting, specifying the limiting distribution and statistics of it have remained open problems since the protocol was introduced. In our main result we describe the limiting distribution of the runtime. We show that it does not converge, and that it becomes, after the appropriate normalization, asymptotically periodic both on the log(2) n as well as on the ln n scale. Additionally, on suitable subsequences we determine the expected runtime and higher moments of it. (C) 2021 Elsevier B.V. All rights reserved.

• Dokumententyp: Zeitschriftenartikel
• Fakultät: Mathematik, Informatik und Statistik > Mathematik
• Themengebiete: 500 Naturwissenschaften und Mathematik > 510 Mathematik
• ISSN: 0304-4149
• Sprache: Englisch