Elsässer, R. ; Lorenz, U. ; Sauerwald, T. (2009)
On randomized broadcasting in Star graphs.
In: Discrete Appl. Math., 157 (1)
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
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 chooses one of its neighbours in G uniformly at random, and sends the information to this neighbour. We show that this algorithm spreads an information to all nodes in a Star graph Sn of dimension n, within O(log N) steps, with high probability, where N denotes the number of nodes in Sn. To obtain this result, we first establish lower bounds on the edge expansion of small subsets of nodes. Then we introduce a simple but powerful technique for estimating the runtime of randomized broadcasting by analyzing the protocol described above in the reverse order. Using this technique we can also simplify the analysis of this algorithm in Hypercubes [U. Feige, D. Peleg, P. Raghavan, E. Upfal, Randomized broadcast in networks, Random Structures and Algorithms 1 (4) (1990) 447–460].
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2009 |
| Autor(en): | Elsässer, R. ; Lorenz, U. ; Sauerwald, T. |
| Art des Eintrags: | Bibliographie |
| Titel: | On randomized broadcasting in Star graphs |
| Sprache: | Englisch |
| Publikationsjahr: | 2009 |
| Ort: | Amsterdam, The Netherlands, The Netherlands |
| Verlag: | Elsevier |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Discrete Appl. Math. |
| Jahrgang/Volume einer Zeitschrift: | 157 |
| (Heft-)Nummer: | 1 |
| Kurzbeschreibung (Abstract): | 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 chooses one of its neighbours in G uniformly at random, and sends the information to this neighbour. We show that this algorithm spreads an information to all nodes in a Star graph Sn of dimension n, within O(log N) steps, with high probability, where N denotes the number of nodes in Sn. To obtain this result, we first establish lower bounds on the edge expansion of small subsets of nodes. Then we introduce a simple but powerful technique for estimating the runtime of randomized broadcasting by analyzing the protocol described above in the reverse order. Using this technique we can also simplify the analysis of this algorithm in Hypercubes [U. Feige, D. Peleg, P. Raghavan, E. Upfal, Randomized broadcast in networks, Random Structures and Algorithms 1 (4) (1990) 447–460]. |
| Fachbereich(e)/-gebiet(e): | 16 Fachbereich Maschinenbau 16 Fachbereich Maschinenbau > Institut für Fluidsystemtechnik (FST) (seit 01.10.2006) |
| Hinterlegungsdatum: | 11 Jul 2013 10:30 |
| Letzte Änderung: | 05 Dez 2024 11:54 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum