UC Riverside

In this thesis we analyze the gathering problem on acyclic graphs in the adhoc radio network framework where the topology of the underlying digraph is unknown. In this problem, each node holds a single message, and the goal is for all nodes to transmit their message to a specified root node. Our main result is a near-optimal lower bound of Ω(n^2/ log n) on the time cost for gathering in acyclic graphs without message aggregation. The key idea is to reduce this problem to a "gathering between layers" problem, isolating the difficulties caused as multiple copies of a message spread through the network.