Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
On Randomized Broadcasting in Star Graphs
verfasst von : Robert Elsässer, Thomas Sauerwald
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
t
an information is placed at one of the nodes of a graph
G
, and in the succeeding steps, each informed node choses one of its neighbors in
G
uniformly at random, and sends the information to this neighbor. We show that this algorithm spreads an information to all nodes in a Star graph
S
n
of dimension
n
within
O
(log (
N
)) steps, with high probability, where
N
denotes the number of nodes in
S
n
. In our proofs, we apply some methods which may be of independent interest, and extend the results of [10] concerning randomized broadcasting in hypercubic graphs.