Messy broadcasting — Decentralized broadcast schemes with limited knowledge |
| |
Authors: | Hovhannes A HarutyunyanPavol Hell Arthur L Liestman |
| |
Institution: | a Department of Computer Science and Software Engineering, Concordia University, Montreal, QC, H3G 1M8, Canadab School of Computing Science, Simon Fraser University, Burnaby, B.C., V5A 1S6, Canada |
| |
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. |
| |
Keywords: | Broadcasting Messy model Upper bound Trees |
本文献已被 ScienceDirect 等数据库收录! |
|