Energy-Efficient Distributed Algorithms: A Survey, Visualizations, and New Results in Radio Networks

Distributed algorithms have been studied for decades, with a particular focus on round and message complexities. Recent works have presented energy-efficient distributed algorithms, where nodes are allowed to sleep, sacrificing the ability to communicate, and the goal is to minimize the amount of time nodes spend in an awake state. This thesis further explores the area and can broadly be divided into three parts. In the first part of this thesis, we provide a literature survey of existing works. Several fundamental graph problems have been studied in this context. Our survey compares the known results from different models, highlights the use of similar techniques, and explores the extent to which the energy complexity of these various problems is understood. In the second part, we study the problem of initialization in single-hop radio networks, which aims to assign unique, consecutive identifiers to all nodes. Previous results on initialization assumed a stronger variant of the radio model, where nodes have sender-side feedback. We introduce an energy-efficient algorithm for partial initialization, which assigns identifiers to a constant fraction of the nodes in the more challenging setting without sender-side feedback. As a consequence, we can simulate existing initialization protocols while maintaining the same energy bound and dropping the reliance on sender-side feedback. Finally, we present visualizations of energy-efficient radio network algorithms for generic simulation, maximal matching, and partial initialization. These visualizations highlight when and where energy is being saved throughout the execution of the algorithms. They also serve as a helpful tool for understanding the algorithms, which may otherwise be difficult to grasp because of the parallel nature of distributed computing.