New Transience Bounds for Long Walks

Date: Thursday, May 24, 2012
Speaker: Thomas Nowak
Venue: IST Austria

Linear max-plus dynamical systems describe the time behavior of a large variety of distributed systems. These include transportation networks, manufacturing plants, and network synchronizers, as well as link reversal algorithms for routing and scheduling. It is known that these systems show a periodic behavior after an initial transient phase. Assessment of the length of this transient phase provides important information on complexity measures of such systems. By identifying parameters in a graph representation of these systems, we give the first potentially subquadratic upper bounds on the transient, which can help during system design.

Posted in RiSE Seminar