BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260519T073643Z
UID:Seminar-dept-1500@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260529T130000
DTEND:20260529T140000
SUMMARY:School Seminar Series
DESCRIPTION:Avery Miller: Labeling Schemes for Wireless Communication\n\nThe 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.\n\n\n\nA 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.\n\n\n\nIn 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.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1500
LOCATION:
END:VEVENT
END:VCALENDAR