Friday, September 17, 2021
10:00 AM
1400 Wegmans Hall
Thomas Hayes
University of New Mexico
Low-Energy Distributed Computation in Radio Networks
Imagine a network of small sensors scattered in a remote environment, and communicating with each other via radio transceivers. These devices have small batteries, and must be sparing with their power usage.

As technological progress leads to smaller devices, the energy cost of radio communication increases compared with other costs, such as local computation. Additionally, the cost of listening for radio messages sent by other nodes becomes comparable to the cost of sending messages. Unfortunately, traditional approaches to network communications, including radio networks, have typically only taken the volume of sent messages into account, while completely ignoring the cost of listening for incoming messages.

We present a new theoretical model that captures this aspect of radio communication networks, and investigate the question of low-energy algorithm design for some basic network communication protocols, such as broadcast, breadth-first search, and maximal matchings. Our main goal is to reduce per-node energy usage exponentially, without sacrificing running time.

This is joint work with Yi-Jun Chang (ETH Zurich), Varsha Dani (RIT), Aayush Gupta (UNM) and Seth Pettie (U. Michigan).

Thomas Hayes is an Associate Professor of Computer Science at the University of New Mexico. His research interests include randomized algorithms (especially Markov chains), probability, statistical physics, combinatorics, distributed systems, and machine learning.