On randomized broadcasting in Star graphs Original Research Article

One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. In this paper, we study the following robust, simple, and scalable randomized broadcasting protocol: at some time image an information is placed at one of the nodes of a graph image, and in the succeeding steps, each informed node chooses one of its neighbours in image uniformly at random, and sends the information to this neighbour.