Labeling Schemes for Wireless Communication

29^th May 2026, 13:00
Avery Miller
University of Manitoba

Abstract

The study of wireless network algorithms is often carried out in the graph-based "radio network model". Each vertex in the graph represents an entity equipped with an antenna, and an undirected edge represents the fact that two entities are within wireless communication range of one another. The possibility of wireless signal interference is modeled in a pessimistic way: if a vertex v has two or more transmitting neighbours in the network, then v does not receive any information at that time. Moreover, a vertex cannot receive any information while it is transmitting.

A long line of research studied efficient deterministic algorithms that solve fundamental communication tasks in radio networks, such as Broadcasting: one designated "source" node has a message that must eventually be received by all other nodes in the network. These algorithms were designed for the "ad hoc radio network" model, which is a challenging scenario where the network nodes have been pre-assigned arbitrary distinct identifiers and have been laid out in an arbitrary topology, all of which is unknown to the algorithm designer. In such a scenario, it is necessary that the node identifiers are distinct so that symmetry can be broken in a deterministic way; so, in a network with n nodes, the identifiers require at least log(n) bits of memory at each node.

In this talk, we will learn about a recent novel direction in the study of deterministic radio network algorithms. If a network administrator knows the topology of the network ahead of time (e.g., if wireless routers will be installed at fixed locations in a building) then perhaps distinct identifiers are not needed. So we ask: what is the smallest number of distinct node labels that can be assigned to nodes such that communication tasks (e.g., Broadcasting) can be solved by a deterministic algorithm? In joint work with Faith Ellen, Barun Gorain, and Andrzej Pelc, we proved that 4 different labels (2-bit labels) are sufficient to solve Broadcasting, regardless of the network size. After presenting this result, the talk will cover some of the follow-up work from the literature and discuss several directions for future research.

Biography

Avery Miller is an Associate Professor in the Department of Computer Science at the University of Manitoba. He completed his M.Sc. and Ph.D. in Computer Science at the University of Toronto under the supervision of Faith Ellen, following a B.Math. from the University of Waterloo. Avery also had the opportunity to carry out postdoctoral research with Andrzej Pelc at the Université du Québec en Outaouais, and with Boaz Patt-Shamir at Tel Aviv University. His research focuses on studying algorithmic complexity, specifically in communication networks or among teams of mobile entities.