Feedbackless Information Gathering on Trees

Graph Theory Seminar
Thursday, April 3, 2014 - 12:05
1 hour (actually 50 minutes)
Skiles 005
University of California, Riverside, CA
Suppose that each node of a rooted tree has a message that it wants to pass up the tree to the root. How can we design a protocol that guarantees all messages (eventually) reach there without being interfered with by other messages, if the nodes themselves do not know the underlying structure of the tree, or even whether their previous messages were successfully transmitted or not? I will describe (near optimal) answers to several variations of this problem, based on joint work with Marek Chrobak (UCR), Laszek Gasieniec (Liverpool) and Dariusz Kowalski (Liverpool).