The energy complexity of broadcast

DOI10.1145/3212734.3212774MaRDI QIDQ5197671zbMATH OpenOpenAlexFDO

Authors Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, Seth Pettie

Publication date 19 September 2019

Published in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.01800

zbMATH Keywords

broadcastdistributed algorithmenergy-aware computingwireless network

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: Energy is often the most constrained resource in networks of battery-powered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (transceiver usage) not computation. As an imperfect proxy for true energy usage, we define energy complexity to be the number of time slots a device transmits/listens; idle time and computation are free. In this paper we investigate the energy complexity of fundamental communication primitives such as broadcast in multi-hop radio networks. We consider models with collision detection (CD) and without (No-CD), as well as both randomized and deterministic algorithms. Some take-away messages from this work include: 1. The energy complexity of broadcast in a multi-hop network is intimately connected to the time complexity of leader election in a single-hop (clique) network. Many existing lower bounds on time complexity immediately transfer to energy complexity. For example, in the CD and No-CD models, we need $Omega(logn)$ and $Omega(lo{g}^{2}n)$ energy, respectively. 2. The energy lower bounds above can almost be achieved, given sufficient ($Omega(n)$) time. In the CD and No-CD models we can solve broadcast using $O(fraclognloglognlogloglogn)$ energy and $O(lo{g}^{3}n)$ energy, respectively. 3. The complexity measures of Energy and Time are in conflict, and it is an open problem whether both can be minimized simultaneously. We give a tradeoff showing it is possible to be nearly optimal in both measures simultaneously. For any constant $epsilon>0$, broadcast can be solved in $O(D^{1+epsilon}lo{g}^{O(1/epsilon)}n)$ time with $O(lo{g}^{O(1/epsilon)}n)$ energy, where $D$ is the diameter of the network.

Recommendations

• Exponential Separations in the Energy Complexity of Leader Election
• Exponential separations in the energy complexity of leader election
• Energy and Time Efficient Broadcasting in Known Topology Radio Networks
• Efficient algorithms for leader election in radio networks
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization

Cited in

(21)

• Singletons for simpletons revisiting windowed backoff with Chernoff bounds
• Exactly optimal deterministic radio broadcasting with collision detection
• Efficient and competitive broadcast in multi-channel radio networks
• The complexity of finding a broadcast center
• Low-weight superimposed codes and related combinatorial structures: bounds and applications
• Exponential separations in the energy complexity of leader election
• TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION
• Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election
• Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks
• The energy complexity of diameter and minimum cut computation in bounded-genus networks
• Energy-efficient distributed algorithms for synchronous networks
• The energy complexity of diameter and minimum cut computation in bounded-genus networks
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Distributed MIS in O(log log n) Awake Complexity
• Distributed MIS with Low Energy and Time Complexities
• Broadcasting competitively against adaptive adversary in multi-channel radio networks
• Jamming-resistant backoff with polylogarithmic sending and listening cost
• Brief announcement: Low-distortion clustering in bounded growth graphs
• A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP
• Energy efficient alert in single-hop networks of extremely weak devices
• Distributed MIS in O( n) awake complexity

This page was built for publication: The energy complexity of broadcast

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197671)