- Series
- Graph Theory Seminar
- Time
- Thursday, April 3, 2014 - 12:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Kevin Costello – University of California, Riverside, CA
- Organizer
- Prasad Tetali
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).