Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.dam.2010.12.002 | Discrete Applied Mathematics |
Keywords | Field | DocType |
trees,conjectured value,random order,limited knowledge,messy model,upper bound,synchronous anonymous communication model,exact bound,decentralized broadcast scheme,broadcasting,worst case analysis,messy broadcasting | Broadcasting,Combinatorics,Vertex (geometry),Upper and lower bounds,Broadcasting (networking),Models of communication,Mathematics,Case analysis,Broadcast communication network,Network structure | Journal |
Volume | Issue | ISSN |
159 | 5 | Discrete Applied Mathematics |
Citations | PageRank | References |
2 | 0.37 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hovhannes A. Harutyunyan | 1 | 206 | 28.18 |
| Pavol Hell | 2 | 2638 | 288.75 |
| Arthur L. Liestman | 3 | 1240 | 169.30 |