ICS Theory Group

Spring 2017: Theory Seminar
Bren Hall, Room 1423, 1:00pm


June 2, 2017:

Faster Information Gathering in Ad-Hoc Radio Tree Networks

Marek Chrobak

Abstract: We study information gathering in ad-hoc radio networks. Initially, each node of the network has a piece of information called a rumor, and the overall objective is to gather all these rumors in the designated target node. The ad-hoc property refers to the fact that the topology of the network is unknown when the computation starts. Aggregation of rumors is not allowed, which means that each node may transmit at most one rumor in one step. We focus on networks with tree topologies, that is we assume that the network is a tree with all edges directed towards the root, but, being ad-hoc, its actual topology is not known. We provide two deterministic algorithms for this problem. For the model that does not assume any collision detection nor acknowledgement mechanisms, we give an O(n*loglog n)-time algorithm, improving the previous upper bound of O(n*logn). We also show that this running time can be further reduced to O(n) if the model allows for acknowledgements of successful transmissions.

(Joint work with Kevin Costello.)

Short bio: Marek Chrobak is currently Professor of Computer Science at University of California, Riverside. Born in Poland, he received his PhD from Warsaw University in 1985, then held an assistant professor position at Warsaw University until 1987, when he moved to UCR and stayed there ever since, enticed by its friendly atmosphere, sunny weather, and proximity to nature. In his research, he is generally interested in theoretical computer science, with his current research topics including offline and online approximation algorithms, information dissemination in radio networks, and job scheduling problems, although in the past he also tried his luck in other areas, including automata theory and bioinformatics.