Elsässer, R. ; Lorenz, U. ; Sauerwald, T. (2007)
Agent-based randomized broadcasting in large networks.
In: Discrete Applied Mathematics, 155 (2)
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
Mobile agents are software abstractions that can migrate across the links of a network. They naturally extend the object oriented program style and nicely correspond to agents as examined in game theory. In this paper, we introduce a simple, robust, and efficient randomized broadcast protocol within this mobile agent programming paradigm. We show that by using this scheme, broadcasting enquiries in a random graph of certain density O(ln n) steps, where n denotes the number of nodes in the graph. Then, we consider bounded degree graphs and prove that we are able to distribute an information among all nodes in O(D) steps, where n denotes the diameter of the graph. We also show that, in contrast to traditional randomized broadcasting (TRB), graphs exist in which agent-based randomized broadcasting requires Ω(n²) steps. On the other hand, some graphs which require Ω(n ln n) steps to spread the information in the traditional broadcast model, allow very fast agent-based broadcasting. It should be noted that the previously mentioned results are guaranteed with probability 1-o(1/n).
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2007 |
| Autor(en): | Elsässer, R. ; Lorenz, U. ; Sauerwald, T. |
| Art des Eintrags: | Bibliographie |
| Titel: | Agent-based randomized broadcasting in large networks. |
| Sprache: | Englisch |
| Publikationsjahr: | 2007 |
| Ort: | Amsterdam |
| Verlag: | Elsevier |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Discrete Applied Mathematics |
| Jahrgang/Volume einer Zeitschrift: | 155 |
| (Heft-)Nummer: | 2 |
| Kurzbeschreibung (Abstract): | Mobile agents are software abstractions that can migrate across the links of a network. They naturally extend the object oriented program style and nicely correspond to agents as examined in game theory. In this paper, we introduce a simple, robust, and efficient randomized broadcast protocol within this mobile agent programming paradigm. We show that by using this scheme, broadcasting enquiries in a random graph of certain density O(ln n) steps, where n denotes the number of nodes in the graph. Then, we consider bounded degree graphs and prove that we are able to distribute an information among all nodes in O(D) steps, where n denotes the diameter of the graph. We also show that, in contrast to traditional randomized broadcasting (TRB), graphs exist in which agent-based randomized broadcasting requires Ω(n²) steps. On the other hand, some graphs which require Ω(n ln n) steps to spread the information in the traditional broadcast model, allow very fast agent-based broadcasting. It should be noted that the previously mentioned results are guaranteed with probability 1-o(1/n). |
| Fachbereich(e)/-gebiet(e): | 16 Fachbereich Maschinenbau 16 Fachbereich Maschinenbau > Institut für Fluidsystemtechnik (FST) (seit 01.10.2006) |
| Hinterlegungsdatum: | 11 Jul 2013 10:40 |
| Letzte Änderung: | 05 Dez 2024 12:02 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum