Asynchronous broadcasting with bivalent beeps
From MaRDI portal
Abstract: In broadcasting, one node of a network has a message that must be learned by all other nodes. We study deterministic algorithms for this fundamental communication task in a very weak model of wireless communication. The only signals sent by nodes are beeps. Moreover, they are delivered to neighbors of the beeping node in an asynchronous way: the time between sending and reception is finite but unpredictable. We first observe that under this scenario, no communication is possible, if beeps are all of the same strength. Hence we study broadcasting in the bivalent beeping model, where every beep can be either soft or loud. At the receiving end, if exactly one soft beep is received by a node in a round, it is heard as soft. Any other combination of beeps received in a round is heard as a loud beep. The cost of a broadcasting algorithm is the total number of beeps sent by all nodes. We consider four levels of knowledge that nodes may have about the network: anonymity (no knowledge whatsoever), ad-hoc (all nodes have distinct labels and every node knows only its own label), neighborhood awareness (every node knows its label and labels of all neighbors), and full knowledge (every node knows the entire labeled map of the network and the identity of the source). We first show that in the anonymous case, broadcasting is impossible even for very simple networks. For each of the other three knowledge levels we provide upper and lower bounds on the minimum cost of a broadcasting algorithm. Our results show separations between all these scenarios. Perhaps surprisingly, the jump in broadcasting cost between the ad-hoc and neighborhood awareness levels is much larger than between the neighborhood awareness and full knowledge levels, although in the two former levels knowledge of nodes is local, and in the latter it is global.
Recommendations
Cites work
- A survey of gossiping and broadcasting in communication networks
- A trade-off between information and communication in broadcast protocols
- Activating anonymous ad hoc radio networks
- An \Omega(D\log (N/D)) Lower Bound for Broadcast in Radio Networks
- Centralized asynchronous broadcast in radio networks
- Deploying wireless networks with beeps
- Fast broadcasting and gossiping in radio networks
- Fault-tolerant broadcasting and gossiping in communication networks
- Information Dissemination in Trees
- Methods and problems of communication in usual networks
- Randomized broadcast in networks
- The computational power of beeps
- Time of Deterministic Broadcasting in Radio Networks with Local Knowledge
Cited in
(5)
This page was built for publication: Asynchronous broadcasting with bivalent beeps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835032)
