Messy broadcasting — Decentralized broadcast schemes with limited knowledge
| Autor: | Arthur L. Liestman, Hovhannes A. Harutyunyan, Pavol Hell |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
business.industry
Applied Mathematics Broadcasting Network structure Upper and lower bounds Trees Vertex (geometry) Random order Models of communication Broadcast communication network Computer Science::Networking and Internet Architecture Discrete Mathematics and Combinatorics business Algorithm Messy model Upper bound Computer Science::Information Theory Computer network Mathematics Case analysis |
| Zdroj: | Discrete Applied Mathematics. 159(5):322-327 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2010.12.002 |
| Popis: | We consider versions of broadcasting that proceed in the absence of information about the network. In particular, the vertices of the network do not know the structure of the network or the starting time, originator, or state of the broadcast. Furthermore, the protocols are not coordinated. This synchronous anonymous communication model has been called messy broadcasting. We perform a worst case analysis of three variants of messy broadcasting. These results also provide upper bounds on broadcasting where every vertex simply calls each of its neighbors once in random order. We prove exact bounds on the time required for broadcasting under two variants and give a conjectured value for the third. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect